Название местности предположительно происходит от слова «ольха»: рядом протекал ручей Ольховец, сохранилась также Ольховская улица. Деревянный храм упомянут на этом месте в 1687 году, каменный появился в 1714–31 на средства Петра I и царевны Прасковьи Ивановны, дочери Ивана V. Строительство затянулось из-за запрета каменных работ на территории всей России, кроме Петербурга. Это здание в дальнейшем перестраивалось.

Именно здесь в 1799 году был крещен А.С. Пушкин.

В 1-й четверти XIX века перестроены верхние ярусы колокольни. В 1837 году основная часть церкви была полностью разобрана: началось строительство нового грандиозного здания по проекту архитектора Е.Д. Тюрина, завершенное к 1845 году. Огромный храм и сегодня доминирует над Елоховской площадью. Колокольня, пышно украшенная колоннами по углам ярусов, – одна из самых высоких в Москве.

В 1889 году трапезная была надстроена архитектором П. П. Зыковым. После революции и закрытия кремлевских церквей, храма Христа Спасителя, а также церкви Богоявления в Дорогомилове Елоховский храм получил статус соборного, неподалеку разместилась канцелярия митрополита Сергия (Страгородского). Попытки закрыть Богоявленский собор предпринимались, но ни одна из них не достигла своей цели. После окончания войны он официально получил статус патриаршего собора и кафедры Патриархов Московских и всея Руси, который сохранялся за ним до 1991 года.

Все центральные богослужения Русской православной церкви и ее крупнейшие события в советскую эпоху проходили именно здесь. В 1943–90 годах в соборе происходила интронизация новых Патриархов Московских и всея Руси. Двое из них были здесь же похоронены: патриарх Сергий в 1944 году и патриарх Алексий II в 2008. Их надгробия можно увидеть, соответственно, в северном и южном приделах.