При настоятельстве отца Иосифа Зотовича Соколова было затеяно большое дело построения нового каменного храма вместо старенького деревянного. Ходатайство об этом началось в декабре 1839 года, когда было подано прошение на имя митрополита Московского и Коломенского Филарета. Его подписали: «Коломенской округи вотчины княгини Багратион села Горы Введенской церкви священник Иосиф Зотов Соколов с причетниками, вотчинник в доверенности бурмистр Иван Трофимович Крюков со всеми прихожанами». В нем просители сообщали, что из-за многолюдства прихода старая деревянная церковь стала тесной: «Почему мы с Божией помощью имеем усердное желание соорудить вместо деревянной каменную церковь во имя Введения во храм Пресвятой Богородицы с двумя приделами: 1) во имя святителя Николая Чудотворца; 2) мученицы Параскевы. На которую церковь план и фасад прилагаем при сем прошении на Вашего Высокопреосвященства высокое утверждение и просим всенижайше на окопреосвященство милостивого отца и архипастыря принять прошение и о просимом учинить Вашего Высокопреосвященства милостивейшее решение». Священник Иосиф Зотович Соколов, дьякон Ермолай Васильевич Горский, дьячок Иван Прохоров и пономарь Алексей Андреев подписались сами. За церковного старосту, по неграмотности оного, за его просьбой Денис Борисов, крестьянин деревни Марково, «руку приложил». Также подпись поставил «горской вотчины по доверенности бурмистр Иван Крюков. Прихожанин сельца Бабурино помещик, отставной штабс-капитан Михаил Гордеевич, сын Юкичев, того же сельца дворянин Андреян Пантелеевич, сын Телегин, того же сельца Бабурино из дворян канцелярист Михаил Сидорович Богданов, того же сельца Бабурино из дворян Иван Петрович Айдаров. Житель деревни Стребковой Ефим Николаев руку приложил. По поручению прихожан – жителей села Горы – за их неграмотностью руку приложил крестьянин того же села Горы Григорий Давыдович Соломатин. Села Марково крестьянин Кондратий Валаамов руку приложил. Села Гор крестьяне Семен Кондратов, Евсей Климов, Терентий Федосеев. За неграмотных крестьян деревни Марково Федор Ефимов руку приложил. За крестьян деревни Варищи крестьянин Михаил Родионов руку приложил. Крестьянин Игнат Алексеев». По этому прошению журнальным постановлением присутствия консистории от 16 февраля 1840 года определено: «Предписать духовному правлению, чтобы истребовало от просителей для отклика в комиссию для строений при губернском правлении в Москве профили и смету на построение и представило в консисторию». В мае через Коломенское духовное правление благочинному, священнику Преображенской церкви села Бояркино иерею Амвросию Уварову, было предписано истребовать от священнослужителей и прихожан Введенской церкви села Горы сведения о строительных планах и суммах сметы, потребных на строительство церкви. Проект храма взялся составлять Сидор Сергеевич Вальцев, опытный архитектор, носивший чин титулярного советника. Этот зодчий немало построил в Москве, в том числе и в самом Кремле, где он работал при надстройке Большого Кремлевского дворца и в иных местах. Комиссия для строения в Москве, рассмотрев составленные Вальцевым фасад и план, признала, что по части архитектурных правил претензий к ним нет, и утвердила их подписями. Так как из полученных сведений выходило, что каменный храм решили строить на совершенно новом месте, то в августе того же года губернским архитектором был послан в село Горы его помощник Александров, которому было поручено свидетельствовать место под построение нового каменного храма. Кроме господина Александрова и причта Введенской церкви, место под застройку осматривал благочинный села Бояркино священник Амвросий Уваров. Совместно этими лицами был составлен следующий документ: «Мы, нижеподписавшиеся, местное положение для строительства нового храма с колокольней в натуре свидетельствовали, и оказалось, что оное место находится напротив крестьянских дворов того села, возвышенное, от жилищ в дальнем расстоянии в безнаселенном месте. К построению упомянутого храма удобное и приличное. Грунт же земли по его испытанию оказался от поверхности глубиной в два с половиной аршина, твердый, каменистый. В чем сие и удостоверяем нашими подписями». Смету постройки составлял архитектор Вальцев, войдя во все тонкости и учтя все мелочи. «Потребно под церковь и церкви с колокольней потребуется 825 тысяч штук. За каждую тысячу 13 рублей с доставкой на место. Потребно 10 725 рублей. За работу с тысячи кирпичей от низа до верха – по 7 рублей. Потребно 5 775 рублей. Белого камня для цоколя и паперти длиной 1 аршин и шириной 5 вершков, толщиной в 4,5 вершка – 800 штук. Белый камень свой, а забутовку и положение каждого камня на место по 40 копеек. Итого нужно 320 рублей. Белого камня для карниза длиной аршин, шириной 5 вершков, толщиной 4,5 вершка потребно 385 штук. За каждый камень по рублю, итого потребно 385 рублей, еще по рублю за обделку и положение, еще 385 рублей (всего, стало быть, 770 рублей). Сортового камня для ручной поделки – шеек, уборки окон и т.д. (длиной ¾ аршина) – 500 камней по 50 копеек за каждый, выходит 250 рублей. За отделку и положение на место еще по 50 копеек каждый, еще 250 рублей (итого 500 в общем). Итого: 18 750 рублей. Для обделки углов материал на 60 рублей. Связного железа на нижний этаж… в колокольню и обухами, засовами и прочим – по 35 копеек фунт, а потребно 375 пудов, по 6 рублей пуд, потребуется 2250 рублей и за всю работу оптом 300 рублей. Кровельное железо на крышу и купол – по 6 листов пуд, 1632 листа, 272 пуда по 10 рублей за пуд, 2720 рублей. За обрешечивание крыши на церкви и колокольне, плотницкие работы, главы, шпили, с покрытием железом, клей и остальные материалы, кроме подрядчиковых денег за всю работу, оптом 1000 рублей. В окна решетки железные – 17 штук, за каждую 50 рублей, итого 850 рублей. Оконные рамы дубовые – 17 штук, за каждую раму по 10 рублей, 170 рублей всего. В окна трибуна итальянские рамы – 4 штуки, за каждую по 20 рублей, итого 80 рублей. Итого: 26 240 рублей. За [изготовление] фрамуг в трибуне оптом – 100 рублей. За сооружение в церкви четырех печей (с материалами и приборами) – по 150 рублей за печь. Всего 600 рублей. На сооружение вытяжки железа на 400 рублей. Задвижку обточить – 450 рублей. На купол, леса, гвозди положено примерно 150 рублей. За изготовление и навеску входных дверей, клиросов, шкафов для книг в алтаре, лестницы в колокольне, плотницкие работы во дворе – оптом 200 рублей. Телеги, доски опалубки, лесов, стремянок и прочего – доски свои. Итого: 28 140 рублей. На непредвиденные случаи 2 800 рублей. Всего же полагается 30 940 рублей». Под сметой подписался Сидор Вальцев, носивший чин титулярного советника. Утвердил архитектор Козневский. При проверке, произведенной консисторией, оказалось, что «означенной суммы, с умеренной отделкой и экономическим распоряжением, будет достаточно». Разрешение на построение нового храма было дано с условием, чтобы постройка возводилась на одобренном помощником губернского архитектора Александровым месте «согласно рассмотренному плану, под надзором опытного архитектора, из хорошего материала, чтобы работы производились знающими мастеровыми людьми. Для чего выдать священнику со старостой храмоздательную грамоту». Работы по возведению и отделке храма были весьма недурно организованы. Если перестройка Сергиевского храма заняла четыре года, то построить и полностью отделать каменную трехпрестольную церковь Введения во храм Пресвятой Богородицы с приделами во имя святителя Николая Чудотворца и святой мученицы Параскевы удалось менее чем за год, и 17 сентября 1841 года храм освятили. На первых порах даже состав причта остался все тот же, от старого храма. Настоятелем был священник Иосиф Зотович Соколов, дьяконом оставался Ермолай Васильевич Горский и пономарь оставался старый, Алексей Андреев. Новым был только дьячок, да и то новым относительно. Незадолго перед тем, как было начато строительство каменной Введенской церкви, прежнего дьячка Иоанна Прохорова сменил на приходе Василий Матвеевич Всехсвятский. Сам сын дьячка, Василий Всехсвятский, вышел из низшего отделения Коломенского духовного училища в 1839 году, просил в Духовном правлении места, и его 29 апреля 1840 года определили в сторожа при правлении. В августе того же года его определили в дьячки к Введенской церкви села Горы.