A new challenge confronted Bishop Anastasios with the coming of a new decade. In January 1991, the Patriarchate of Constantinople elected Anastasios to go to Albania as “Patriarchal Exarch” with the mandate to contact Orthodox people irrespective of their ethnic origin and re-establish the Orthodox Autocephalous Church of Albania. The Orthodox Church in Albania had been decimated after forty years of the most severe persecution. Before the country had finally overthrown its yoke of communism, the number of Orthodox clergy had diminished from 440 in  the 1940’s to 22 in 1990. Once again, the opportunity to revive a Church on the brink of collapse confronted Bishop Anastasios.
    Yannoulatos saw this new challenge as an opportunity to synthesize the elements of his life. Before communism, Albania was a country of 69% Muslims. Bishop Anastasios had written a book and many articles on Islam. The political uncertainties which the church faced with the government was something he was accustomed to from his work in East Africa. The challenge to resurrect a local church from an atheistic abyss would require a miracle, similar to the miracle required in the early 1960s to establish an external Orthodox mission. But as his life has shown, Bishop Anastasios believes in miracles.
    Overall, the priorities of Bishop Anastasios in Albania during his first two years of episcopacy were to train local leaders, perform responsible pastoral work to the twenty-one  percent of the population that claimed an Orthodox heritage, and to open dialogue and bridges to people of other faiths. In response to his leadership, the church quickly established an Orthodox seminary with more than eighty students. The number of clergy increased from eleven to fifty-six within the first two years of his episcopacy. And the future looks bright with the influx of converts stemming from his outreach to young atheists and Muslims.