Charalambides was ordained to the diaconate on 6 January 1963 and to the priesthood on 17 November 1968 for service in the Greek Orthodox Metropolis of France.
He was appointed in 1972 as protosyngellos (episcopal vicar) for the southern region of France, with his base in Nice.
While continuing his previous responsibilities, he also became secretary of the Assembly of Orthodox Bishops of France, lector at St. Sergius, and professor of patrology at the Roman Catholic seminary of Nice.
In 1996, the Ecumenical Patriarchate restored the Estonian Orthodox Church as an autonomous entity under its protection, following the independence of Estonia from the Soviet Union.
A General Assembly of the church elected Stephanos as Metropolitan of Tallinn and All Estonia.