Fillimi i një dhjetëvjeçari të ri, e përballi Episkopin Anastas me një sfidë të re. Në janar të vitit 1991, Patriku i Kostandinopojës e zgjodhi Anastasin të shkonte në Shqipëri si “Eksark Patriarkal”, me mandatin që të takohej me orthodhoksët, pavarësisht nga origjina e tyre etnike dhe të ringjallte Kishën Orthodhokse Autoqefale të Shqipërisë. Kisha Orthodhokse në Shqipëri ishte shkatërruar pothuajse prej dyzetë vjetësh persekutimi të ashpër. Para se vendi të hidhte tutje regjimin komunist, numri i klerikëve ishte zvogëluar nga 440 në vitin 1940, në 22 në vitin 1991. Edhe një herë, Episkopi Anastas u përball me mundësinë për të rilindur një Kishë që ishte shkatërruar.
Anastasi e pa këtë sfidë të re si një mundësi për të mbledhur së bashku të gjitha pjesët e jetës së tij. Përpara komunizmit, Shqipëria ishte një vend me 69% muslimanë. Episkopi Anastas kishte shkruar një libër dhe shumë artikuj për Islamin. Pasiguria politike me të cilat përballej Kisha ishte diçka me të cilën ai ishte mësuar tashmë nga puna e tij në Afrikën Lindore. Sfida për të ringjallur një Kishë lokale në një boshllëk ateist do të kërkonte një mrekulli, të ngjashme me atë të fillimeve të viteve 60-të, kur ai kërkonte të ndërtonte një misionarizëm orthodhoks të jashtëm. Por, ashtu siç kishte treguar jeta e tij, Episkopi Anastas besonte në mrekullitë.
Mbi të gjitha, ai, gjatë dy viteve të para i dha përparësi përgatitjes së udhëheqësve vendas, u kujdes për 21% të popullsisë, që thoshte së kishte trashëgimi orthodhokse, dhe për të hapur dialogun dhe urat me njerëz të besimeve të tjera. Nën udhëheqjen e tij, Kisha menjëherë hapi një seminar. Numri i studentëve u rrit nga 11 në 52 gjatë dy viteve të parë të punës së tij dhe e ardhmja dukej e ndritshme nga numri i madh i të pagëzuarve dhe nga puna e tij me të rinjtë.
