Раньше село Владыкино называлось Вельяминово по фамилии первых его владельцев, знатных бояр Вельяминовых. В XIV в. село было передано Богоявленскому монастырю. В последствии оно несколько раз меняло своих хозяев, это всегда были высокопоставленные знатные люди. Но особо благодатный период для села наступил 360 лет назад: в 1653 г. Вельяминово перешло во владение Святейшего Патриарха Никона. С этого времени местность получила ныне существующее название Владыкино и до конца Патриаршества составляло домовую вотчину Святейших Патриархов.

Деревянная церковь во имя Рождества Пресвятой Богородицы появилась здесь еще в 1627 г. Ее построил князь Иван Иванович Шуйский взамен прежней обветшавшей церкви святителя Николая.

В церкви Рождества Пресвятой Богородицы во Владыкине служили Литургию Патриарх Иоаким (6 мая 1683 г., 15 июля 1685 г., 18 октября 1688 г.), Патриарх Андриан (9 декабря 1693 г., 12 июня 1695 г.). 19 мая 1690 г. село Владыкино посетил государь Петр Алексеевич. При патриархах во Владыкине существовали патриаршие палаты, сады и пруды. В 1722 г. село было пожаловано во владение Преосвященному Феофану (Прокоповичу) архиепископу Псковскому и Нарвскому, а по его смерти вернулось Богоявленскому монастырю.

Деревянная церковь Рождества Пресвятой Богородицы несколько раз поновлялась и перестраивалась. В середине XIX в. деревянный храм был разобран. Стараниями купца Гавриила Толоконникова и священника села Владыкина Василия Нечаева был построен новый каменный трехпрестольный храм Рождества Пресвятой Богородицы, который в 1859 г. освятил митрополит Московский Филарет (Моск. епарх. вед., № 48, 1870 г.).

В конце XIX в. при настоятеле протоиерее Иоанне Протопопове в храме были проведены дорогостоящие ремонтные и реставрационные работы, были поновлены живопись на стенах и иконостас. О. Иоанн в 1896 г. открыл при храме одноклассную церковно-приходскую школу. С ним с 1900 г. служил диакон Иоанн Хрусталев, который после его смерти в 1917 г. был рукоположен во священника. В 1937 г. протоиерей Иоанн Хрусталев и служившие с ним протодиакон Сергий Станиславлев и чтец Николай Некрасов были арестованы. О. Иоанн Хрусталев был расстрелян на полигоне в Бутово, а протодиакон Сергий и чтец Николай умерли в ссылке. 27 марта 2007 г. решением Священного Синода они были причтены к сонму новомучеников и исповедников Российских.

Вблизи храма Рождества Пресвятой Богородицы во Владыкине в 1936 г. была похоронена св. блж. Матрона Анемнясевская (день преставления 16/29 июля). А еще раньше, в 1928 г. в ограде храма была похоронена актриса Мария Ермолова.

Храм никогда не закрывался. В 1938 г. старосте храма Василию Васильевичу Флянову удалось спасти храм от закрытия. Этот замечательный человек за свои церковные заслуги был трижды награжден патриаршими грамотами за подписью Святейших Патриархов Тихона, Сергия и Алексия I.

В храме находятся древние и драгоценные по своему письму иконы XVII в.: икона Спасителя, Смоленская и Казанская иконы Божией Матери, а также иконы начала XVI в.: Рождества Пресвятой Богородицы и святителя Николая. Смоленская икона Божией Матери почитается как чудотворная. Помощь от нее жители Владыкина и окрестных селений получили в холерный 1848 г., когда с обнесением иконой крестным ходом этих селений холера не получила распространения в этой местности. Известны и многие другие исцеления от Смоленской иконы. В конце XIX в. от нее исцелилась отроковица Антонина, и чаяниями ее матери Анны Соколовой в благодарность за исцеление в село Владыкино была привезена икона Скоропослушница, написанная на Святой горе Афон.

В последние десятилетие в храме ведутся большие ремонтные и реставрационные работы. Древним иконам возвращен их первоначальный вид, отреставрированы и позолочены иконостас и киоты. Возрождается и приходская жизнь. При храме действует воскресная школа, молодежный кружок и школа для взрослых, работают катехизаторы и миссионеры.

В храме Рождества Пресвятой Богородицы служил старейший клирик Москвы, почетный настоятель прот. Симеон Сиранчук. Он преставился ко Господу 19 сентября 2013 г. и по благословению Святейшего Патриарха Кирилла был похоронен в ограде храма.