В 1892 года православным Свято-Владимирским братством и настоятелем посольского храма в Берлине протоиереем Алексеем Мальцевым, было приобретено два участка земли: один – для устройства православного кладбища в пригородной тогда деревне Тегель и другой – для строительства Братского дома, предназначением которого была благотворительность и просветительская деятельность. В 1893 году при участии Свято-Князь-Владимирского братства на купленных участках был заложен златоглавый православный храм во имя равноапостольных Константина и Елены.
Создателем Свято-Князь-Владимирского братства был протоиерей Алексей Мальцев. Братство было организовано для помощи нуждающимся российским подданным любого христианского исповедания и православным христианам любой национальности. Членами Братства были святитель Феофан Затворник, праведный Иоанн Кронштадтский, равноапостольный Николай Японский, священномученик митрополит Владимир (Богоявленский), преподобномученица великая княгиня Елизавета Феодоровна, страстотерпец Великий князь Михаил Александрович (брат императора Николая II), королева Вюртембергская Ольга Николаевна (дочь Николая I), великий князь Алексей Александрович, великий князь Сергей Александрович, великий князь Павел Александрович, великий князь Георгий Михайлович, великий князь Михаил Михайлович, князь Владимир Павлович Палей, принцесса Альтенбургская и герцогиня Мекленбургская Елена Георгиевна, граф М.Н. Муравьёв, граф А.В. Голенищев-Кутузов, генерал-адъютант И.Л. Татищев, контр-адмирал Ф.В. Дубасов, К.К. Грот, В.А. Дашков, композитор и дирижер А.Г. Рубинштейн и многие другие.
Церковь строилась по проекту, присланному из России, руководил постройкой местный архитектор Бомм. По распоряжению Александра III в Тегель доставили 4 тонн земли, собранной в 20 российских губерниях, которая была распределена по всему кладбищу. Из России привезли и саженцы деревьев – липы, дуба, клёна, – чтобы почившие на чужбине были похоронены в родной земле под сенью русских деревьев. С течением времени кладбище стало мемориалом русской эмиграции в Германии. Здесь покоятся представители прославленных дворянских родов, министров, академиков, генералов, священнослужителей, писателей, казачьих атаманов, унтер-офицеров и рядовых: князь Федор Голицын, архитектор Михаил Эйзенштейн (отец знаменитого режиссера), Владимир Набоков (отец известного писателя), семейство графов Воронцовых-Дашковых, княжна Мария Мещерская, российский посол С.Н. Свербеев. Здесь покоятся, сестра марины Цветаевой, племянник композитора Римского-Корсакова.