История храма Всех Святых в селе Всехсвятском началась, когда село носило имя Святые Отцы. По легенде, здесь около 1398 года был основан мужской монастырь с соборным храмом, а отшельники жили в окрестном лесу в хижинах. Село Святые Отцы упоминается в конце XV века в духовной грамоте князя Ивана Юрьевича Патрикеева, двоюродного брата великого князя московского Ивана III, согласно которой он передавал это село с другими угодьями своему сыну.
Одни историки согласны с тем, что здесь действительно до XV века стоял монастырь с храмом в честь Всех Святых, другие считают, что собор монастыря был освящен в честь VII Вселенского собора Святых Отцов, отчего и произошло название села. На VII Вселенском соборе, проходившем в Никее, голос иконоборцев был заглушён волей большинства. То есть тот собор утвердил иконопочитание.
Был здесь монастырь или не был, но храм, правда уже приходской, упоминается в XVI веке. В 1608 году село занимал Лжедмитрий II. По преданию, перед бегством он зарыл в селе все свои сокровища.
В конце XVII века село вместе с храмом перешло главе приказа Большой казны, боярину Ивану Михайловичу Милославскому. Иван Михайлович был одним из участников стрелецкого бунта 1682 года и после бунта был лишён управления приказами и удалился в свою вотчину у Святых Отцов. Здесь он скрывался от преследований политических недругов и благоустраивал своё владение. Известно, что в 1683 году по указу Ивана Михайловича церковь была перестроена в камне. И именно по церкви село Святые Отцы было названо Всехсвятским. В 1685 году он умер, к счастью для себя не дожив до нового стрелецкого бунта 1689 года.
Единственная дочь Ивана Михайловича Милославского Федосья Ивановна вышла замуж за грузинского царевича Александра Арчиловича, давнего друга царя Петра, и село Всехсвятское перешло к нему как приданое жены. После смерти Федосьи Ивановны Пётр I именным указом пожаловал село в полную собственность вдовца. Ещё в 1699 году в Москву прибыл сам грузинский царь Арчил II с женой и свитой и поселился во Всехсвятском. Приход грузин в Москву было не началом, а, скорее, результатом дружественных отношений Грузии с Россией, когда Грузия терпела бедствия от своих воинственных иноверных соседей, прежде всего от Османской империи, и просила у православной России защиты и помощи. Так в селе Всехсвятское образовалась колония грузин, а само село попало на страницы истории многовековых взаимоотношений России и Грузии. Позднее началась новая волна грузинских августейших иммигрантов. В Москву приехал царь Вахтанг IV с семьей, духовенством и многочисленной свитой. Грузинский правитель тоже отправился во Всехсвятское. Поскольку численность грузинской колонии в Москве оказалась очень высока – несколько тысяч человек, – ей были отведены и земли на Пресне, в районе нынешних Грузинских улиц и Тишинки. Так в старой Москве образовалось два главных грузинских поселения: древнейшее находилось во Всехсвятском, второе – на Пресне.
Царевич Александр Арчилович, у которого во Всехсвятском не раз гостил Пётр I, попал во время Северной войны в плен и умер в Стокгольме в 1711 году, не оставив потомства. Всехсвятское перешло к его сестре Дарье Арчиловне. Она и построила здесь в 1733–1736 годах новую прекрасную церковь, которая дожила до наших дней.
Главный престол освящён в честь Всех Святых, а два придела – в честь иконы «Всех Скорбящих Радость» и во имя праведных Симеона Богоприимца и Анны Пророчицы.
Новопостроенная церковь стала центром грузинской колонии в Москве. В самом конце XVIII века очередной владелец Всехсвятского села, князь Георгий Бакарович, обновил храм и устроил на левом клиросе царское место. Это было время расцвета Всехсвятского. Здесь стоял Летний дворец с роскошным садом, оранжереями и прудом, по которому гости совершали водные прогулки в гондолах. А в престольные праздники во Всехсвятском происходили большие народные гулянья. В 1812 году и храм, и село разорили войска Наполеона, но стараниями царевича Георгия всё было восстановлено и храм благолепно украшен.
Храм Всех Святых стал усыпальницей московских грузин. На его погосте был похоронен Иван Александрович Багратион, отец знаменитого генерала Петра Ивановича Багратиона. Сам полководец и поставил памятник на отцовской могиле.
После прокладки шоссе в 30–е годы XIX века во Всехсвятском начались массовые народные гулянья. Если в соседнем Петровском парке предпочитала веселиться знать, то в более отдалённом Всехсвятском – простые москвичи. Здесь же, во Всехсвятской роще, в 1878 году был устроен Александровский приют для увечных и престарелых воинов только что отгремевшей Русско-турецкой войны.