התקופה שבה החלו יהודי אתיופיה לעלות לישראל הייתה תקופה קשה. רבים חזרו מהמסע, והיו צריכים עידוד. רבים המתינו בכפרי-מעבר, עד שתיפתח הדרך. בנוסף, בתים רבים עמדו ריקים.
באותם ימים שליט אתיופיה, שעמד בראש הדרג המדיני, מנגיסטו היילה מרים, הכריז שהוא רוצה לקיים שוויון בין הדתות כולן: נוצרים, מוסלמים ויהודים, ללא הבדל. לפיכך יותר ליהודים לבנות בתי כנסת, בכל מקום בו יהודים נמצאים. קֶייס מֶלְקֶה עזריה ניצל את ההזדמנות, ופנה לשלטונות וקיבל אישור לבניית בתי הכנסת. הוא מינה נציגים בכל כפר וכפר, ואחראים לכל אזור. הוא ניצל את הבתים שעמדו ריקים לשם כך. הוא הגיע גם לכפרי-המעבר, שלא היה להם בתי כנסת, וסייע להם.