Первые упоминания о Христорождественской церкви в с. Лебяжье Ставропольского уезда в клировой ведомости за 1849 год. Эта деревянная церковь была построена в 1745 году на средства прихожан. В 1846-1847 годах церковь была перестроена на каменном фундаменте и вновь освящена 05 июня 1848 года. Церковь не отапливалась, не было ни печей, ни труб. Престол в церкви был один во имя Рождества Христова, холодный. Было принято решение о строительстве нового храма, так как русское село основательно выросло и в 1897 году население его составляло 3090 душ обоего пола. К тому же здание деревянной церкви было малой вместимости, да еще и холодное и обветшавшее. По штату храма полагалось 2 священника, один дьякон и псаломщик. При церкви имелись дома для священнослужителей, также деревянные, в настоящее время не сохранились.
В бумагах канцелярии епископа Самарского и Ставропольского от 16 июля 1900 года есть такая запись: «Храмы удовлетворяют потребностям населения, кроме сел: Лебяжье». Принимается решение о строительстве нового каменного храма Рождества Христова вместимостью более 1000 человек. Церковь, предполагается, поставить «кораблем», то есть вытянуть по одной оси с востока на запад алтарь, собственно храм, трапезную и колокольню, кроме того к храмовой части сделать два боковых придела. Автора проекта Христорождественской церкви выяснить не удалось, возможно, это проект по какому-то «образцу».
В 1902 году проект был утвержден строительным отделением Самарского правления. Техническое наблюдение «за работами» на церкви принял на себя Самарский Епархиальный архитектор Тадеуш Северинович Хилинский. Сохранилась его записка: «1902 года 2 дня, Я, нижеподписавшийся, даю настоящую подписку в том, что принял на себя наблюдение с ответственностью в техническом отношении за правильность и прочность работ по постройке каменной церкви в с. Лебяжье Самарской губернии Ставропольского уезда, при чем обязуюсь с начала и конца работ доносить в Самарское Губернское управление. Самарский Епархиальный архитектор Хилинский».
Хилинский Т.С. состоял в должности Самарского Епархиального архитектора более 23 лет. С 1887 года он занимался составлением проектов церквей на территории Самарской губернии. Под его наблюдением возводились «Самарские кресты» в Самаре, а также автор проектов винокуренного завода, зданий магазинов, которые до сих пор сохранились в Самаре. Скончался Самарский губернский инженер, статский советник Хилинский Т.С. 24 ноября 1905 года от чахотки.
Каменный Христорождественский храм был заложен в с. Лебяжье 21 июля 1902 года в нескольких метрах от старой деревянной церкви. 20 августа 1906 года новый храм был построен, а 14 декабря 1908 года освящён.
