Название, по одной версии, произошло от слова «острожек» – укрепление, каким был в древние времена Острогожск, по другой версии, от ближней речки Острогощи. Город также называли Рыбным, потому что здесь велась большая торговля рыбой, привозимой по Сосне с Дона.

В 1652 г. для охранения сосенской линии от татарских набегов, царь Алексей Михайлович вызвал из-за Днепра тысячу черкасов и поселил их в местах татарских переправ. Такое переселение и положило начало Острогожску. Черкасы, прибывшие сюда, имели даже своих священников.

16 августа 1652 г., в день праздника перенесения Нерукотворного Образа Спасителя, воевода Федор Юрьевич Арсеньев, по приказу царя, заложил на месте поселения черкас, крепость с семью бастионами, на старом Острогожском городище, т. е. там, где существовало какое-то более раннее поселение. В нем он построил соборную Троицкую церковь с приделом свт. Николая.

По благословению митрополита Сарского и Подонского Питирима, около 1663 г. в Острогожске был построен Успенский храм с приделом Параскевы Пятницы. При нем был учрежден женский монастырь, просуществовавший до 1786 г. В те же годы была построена Покровская церковь.

Последующая история Острогожска однообразна.

В 1696 г., Петр I, возвращаясь в Москву праздновать свои победы, вызвал в Острогожск гетмана Мазепу, чтобы благодарить его за успехи. И город Острогожск стал свидетелем клятвы гетмана в искренней преданности русскому царю.

В 1721 г. на площади был освящен новый двухэтажный Троицкий собор в итальянском стиле. Первая деревянная Троицкая церковь с Никольским приделом и трапезой была построена в крепости стольником и воеводой князем Федором Юрьевичем Арсеньевым. Закончена она была одновременно с крепостью 7 ноября 1653 г. В камень церковь перестроили в 1721 г. В 1766 г. к церкви пристроили трапезу с колокольней. В этом же году архимандрит Воронежского Акатова монастыря Сампсон освятил в трапезе два престола: 4 мая Введения во храм Пресвятой Богородицы и 6 мая свт. Николая Чудотворца.

13 мая 1780 г. эту каменную церковь стали разбирать для строительства нового большого храма. И пока это строительство продолжалось, богослужения совершались в мужском Преображенском монастыре (каменная церковь Преображения Господня).

Предание связывает перестройку храма с именем очень состоятельного Острогожского сотника Дмитрия Петровича Синельникова, у которого в 1777 г. на Кавказе погиб единственный сын. Потеряв наследника своего громадного капитала, Д.П. Синельников решил употребить его на постройку храма.

С благословения преосвященного Тихона III началось строительство. В нижнем храме три престола. Средний был освящен 30 января 1782 г. преосв. Тихоном III во имя Введения Пресвятой Богородицы во храм. Второй престол освящен был 1 февраля во имя свт. Николая Чудотворца, а третий – 5 февраля во имя Всех святых. В воскресный день 27 июня 1787 г. преосвященным Тихоном III был освящен престол верхнего этажа во имя Святой Живоначальной Троицы.

По кончине Д.П. Синельникова, собору покровительствовала его вдова Наталья Федоровна. В нижнем этаже, ее усердием и трудами острогожского мастера Алексея Лукьяновича Асадченкова, был сделан новый иконостас. Вследствие этого, и престолы переосвящены были в сентябре 1790 г. Воронежским епископом Иннокентием, причем Всехсвятский придел был переосвящен в честь св. Иоанна Богослова.

В 1804 г. Н.Ф. Синельникова выстроила в церковной ограде дом для проживания священнослужителей, а также престарелых вдов и сирот. Эта редкая благотворительница скончалась 15 февраля 1811 г.