Среди русских, в составе экипажей, пришедшей в 1920 году в Северную Африку Русской эскадры были 13 православных священников. Церковные службы проходили на специально оборудованной для этих целей палубе броненосца «Георгий Победоносец» и в церкви святого Павла Исповедника, устроенной в созданном в одном из казематов старого военного форта Джебель Кебир недалеко от Бизерты.
В 1921 году было зарегистрировано культурно-просветительское объединение «Cercle Russe d’Alger» (Русский кружек Алжира), который стал инициатором духовного попечения, пригласил священника и учредил приход. Первым русским священником в Алжире был бывший военно-морской священник протоиерей Евфимий Логодовский, отец архитектора и строителя русского храма в честь Воскресения Христова в Тунисе. В 1928 году он организовал храм святого апостола Андрея Первозванного, для чего использовалось доставленное из Туниса имущество корабельных церквей.
С 1935 года в Алжире стала действовать домовая церковь Святой Троицы, в помощь настоятелю был направлен отец Василий Шустин. Они одновременно, до смерти Логодовского, обслуживали два русских храма. Шустин регулярно совершал поездки по стране с целью духовной опеки соотечественников, проживавших в других местах Алжира.
В 1936 году имущество общины апостола Андрея было передано приходу Святой-Троицы, в его архиве сохранился список, в котором упоминаются: жертвенник, свечной ящик, три аналоя, два подсвечника, хоругви, купель и другая церковная утварь, а также Евангелие и различные книги духовного содержания. Перед Второй мировой войной русская колония в Алжире насчитывала около 500 человек.
При русской общине в Алжире действовала библиотека, сконцентрировалась активная социальная и культурная жизнь, ставился вопрос о покупке земли и строительстве стационарного храма, так председатель ассоциации Лев Павлович Долгушин в октябре 1951 года писал об этом управляющему русскими приходами в Северной Африке архиепископу Пантелеимону.
В 1959 году после признания Францией права Алжира на самоопределение, начался процесс массового отъезда европейцев из страны. К 1968 году в Алжире оставалось всего 12 русских прихожан.
