После разорения Лебедяни в 1613 г. и после сожжения гетманом Сагайдачным города в 1618 г. в малом остроге вновь была выстроена церковь. Возможно, новый собор был освящён в прежнее храмонаименование и именно он упоминается среди построек малого острога Лебедяни в писцовых книгах 1627—1628 гг.: «… соборная церковь древяна клецки с папертью во имя Николы Чудотворца…» И эта церковь сгорела 25 апреля 1662 г. Лишь через три года последовал царский указ о постройке соборной церкви в Лебедяни с тем же храмонаименованием.
В 1703 г. страшный пожар практически полностью уничтожил Лебедянь. Сгорела и крепость, и все строения, находящиеся в ней. В том числе и обветшавшая к тому времени соборная церковь святителя Николая Чудотворца.
Лебедянцами была выстроена новая соборная церковь, освящённая теперь «во имя Пресвятые Богородицы Казанские».
Спустя десятилетие после возведения новой соборной Казанской церкви что-то подвигло жителей города построить ещё один деревянный храм и освятить его в память прежнего собора – во имя святителя Николая Чудотворца. Произошло это около 1715 г. С этого времени оба отдельно стоящих храма – Казанский и Никольский, имевшие один общий причт, именовались соборными храмами города Лебедяни. К 1768 г. обе церкви пришли в такую ветхость, что «в зимнее время от мятели и в летнее время от дождя происходила немалая течь; почему вкладчики пожелали вместо оных соборных ветхих деревянных церквей построить с колокольней одну во имя Казанския Пресвятые Богородицы церковь, с приделом Николая Чудотворца, каменным зданием», которая и была освящена в 1771 г. Старые деревянные соборные храмы были разобраны.
Первоначально была выстроена только храмовая часть с небольшой трапезной и отдельно стоящей колокольней. И только через несколько лет, в конце того же XVIII столетия, их соединили, расширив на запад трапезную часть. Особенностью нового храма стало отклонение его продольной оси и алтаря на 20 градусов к северу, в отличие от большинства других церквей, имевших более чёткую ориентацию восток-запад.
Длина Казанской церкви с колокольней составила 48 арш., ширина — 11 арш., высота храмовой части до верха карниза — 8 арш., высота колокольни до верхнего карниза — 37 арш. В 1846 г. к колокольне были пристроены кирпичная кладовая и караулка.