Первые контакты Александрийского Патриархата с Русской Церковью приходятся на патриаршество Иоакима I Паниса (1487-1567). В 1523 г. он направил делегацию в Москву к Василию III с просьбой оказать материальную помощь Александрийской Церкви, а в 1556 г. посольства Патриарха Александрийского и архиепископа Синайского с аналогичными целями отправились к Иоанну IV Грозному.
В 1593 году Патриарх Мелетий совместно с другими Предстоятелями подтвердил Патриаршее достоинство Предстоятеля Церкви всея Руси и всех Северных стран. Патриарх Александрийский Паисий был первенствующим из православных Предстоятелей на Большом Московском Соборе 1666 года. В 1855 году при содействии святителя Филарета, митрополита Московского и Коломенского, в Москве было открыто Александрийское подворье.
Отношения между Александрийской и Русской Церквами, фактически прерванные революцией 1917 г., были восстановлены в 1943 г. через обмен посланиями Патриархов Московского Сергия и Александрийского Христофора II. Последний присутствовал при настоловании Святейшего Патриарха Алексия I на Поместном Соборе 1945 г. В том же году в ходе визита Святейшего Патриарха Алексия Ι в Египет в Александрии было открыто подворье Патриарха Московского и всея Руси, настоятель которого получил статус экзарха. В 1956 г. в Одессе было открыто подворье Александрийской Православной Церкви.
3 июня 1971 г. Блаженнейший Патриарх Николай VI принимал участие в интронизации избранного Патриарха Московского и всея Руси Пимена. Предстоятель Александрийской Церкви длительное время лечился в России; скончался 10 июня 1986 г. в Московской клинической больнице им. С.П. Боткина. Его преемник Блаженнейший Патриарх Парфений дважды за время своего Предстоятельского служения был гостем Русской Православной Церкви — в 1993 и 1996 гг.
В 1999 г. при Блаженнейшем Патриархе Петре VII Александрийское представительство было переведено из Одессы в Москву. В свою очередь Александрийская Патриархия передала храм святого великомученика Димитрия в Каире в пользование русской общине и для нужд представительства Патриарха Московского при Патриархе Александрийском.
Нынешний Патриарх Александрийский Феодор ΙΙ дважды после избрания на Александрийский престол посетил пределы Русской Православной Церкви. В 2007 г. состоялся официальный визит Его Блаженства в Москву, Киев и Одессу. В 2009 г. Блаженнейший Патриарх Феодор II принял участие в интронизации Святейшего Патриарха Московского и всея Руси Кирилла.
Существует договоренность между Александрийским и Московским Патриархатами о том, чтобы русские священники осуществляли пастырское окормление русскоязычных православных соотечественников, проживающих на Африканском континенте. В настоящее время приходскую деятельность осуществляют клирики Московского Патриархата в Тунисе, Марокко, ЮАР и Египте.
Русские приходы в Тунисе и Марокко были основаны в 1920-х гг. русскими эмигрантами. Действующее с 1945 г. представительство Патриарха Московского и всея Руси при Патриархе Александрийском в 1999 г. получило в пользование храм святого великомученика Димитрия в Каире. С 1998 г. в ЮАР существует приход преподобного Сергия Радонежского. Настоятель храма периодически осуществляет окормление соотечественников как в городах ЮАР (Кейптаун и Дурбан), так и в сопредельных государствах (Мозамбик и Ангола).
29 марта 2010 г. Блаженнейший Папа и Патриарх Александрийский и всей Африки Феодор II, прибывший в Южно-Африканскую Республику с Первосвятительским визитом, посетил русский храм преподобного Сергия Радонежского в Йоханнесбурге. Предстоятель Александрийской Православной Церкви совершил в храме литию по жертвам произошедшего в этот день в московском метро террористического акта.
