Первое документальное упоминание о церкви Богоявления Господня в селе Елохове относится к 1694 году, согласно указу патриарха Адриана. Изначально храм был деревянным и имел придел в честь Благовещения. В начале XVIII века, по указу императора Петра I, было принято решение о строительстве каменного храма. Строительство велось на пожертвования прихожан, включая полковника Воронецкого и царевну Прасковью Ивановну, дочь царя Иоанна V Алексеевича. Кирпич для строительства был предоставлен лично Петром I. Работы продолжались с 1712 по 1731 год, когда храм был освящен архиепископом Подонским и Сарским Леонидом.
В 1780-х годах началась значительная перестройка храма. Была возведена большая каменная трапезная с двумя приделами: Благовещенским и во имя святителя Николая Чудотворца. В этот же период началось строительство колокольни, завершенное к 1806 году. Трапезная и колокольня, выполненные в стиле московского классицизма, сохранились до настоящего времени. В 1799 году в этом храме был крещен Александр Сергеевич Пушкин.
В связи с увеличением числа прихожан в первой половине XIX века было принято решение о строительстве нового, более вместительного собора. В 1835 году началось возведение нового здания по проекту архитектора Евграфа Тюрина. Строительство продолжалось до 1845 года, после чего началась внутренняя отделка, завершенная к 1853 году. Новый храм был освящен митрополитом Филаретом (Дроздовым).
Архитектурно собор представляет собой пятиглавое здание в стиле позднего ампира с купольной ротондой в центре, напоминающей купол собора Святого Петра в Риме. К главному зданию примыкает трапезная, перекрытая крестовыми сводами, и трехъярусная колокольня высотой 65 метров с семнадцатью колоколами. Внутреннее убранство храма богато украшено росписями, выполненными в конце XIX — начале XX века.
В советский период собор оставался действующим, что было редкостью для того времени. В 1943 году, после избрания митрополита Сергия (Страгородского) Патриархом Московским и всея Руси, собор стал патриаршим. В 1945 году здесь состоялась интронизация Патриарха Алексия I. В подклете северного Никольского придела собора похоронены Патриархи Сергий (в 1944 году) и Алексий II (в 2008 году).
В послевоенные годы в соборе проводились реставрационные работы. В 1947 году, к 800-летию Москвы, были обновлены иконостас, киоты и росписи. В 1948 году, к 500-летию автокефалии Русской церкви, для мощей святителя Алексия была создана новая рака. В 1988 году, к 1000-летию Крещения Руси, проведен капитальный ремонт фасадов и фресковой живописи.
