בשנת תרל"א (1871) נבנה חאן במוצא, ושנת ייסודו חקוקה על אבן הקשת במבנה המשמש היום כבית כנסת. החאן נבנה על בסיס מבנה עתיק, שנבנה על-פי המשוער בימי ממלכת ירושלים הצלבנית. הבניין נבנה על ידי יהושע ילין, על מנת לשמש מלון דרכים לעוברים בדרך יפו-ירושלים. בהמשך שימש מרתף המבנה בית לפועלים. בשנת 1905 הגיעה קבוצת תיירים למוצא, בהם הרב בנימין זאב קראוס, רבה של דברצן שבהונגריה, שלמה צבי שי"ק, רבה של העיר קרצאג ואחרים, וכששמעו מיהושע ילין כי אין בית כנסת במקום, יזם הרב קראוס גיוס סכום כסף נכבד לבניית בית הכנסת בתוך מבנה החאן. סיפור הקמתו של בית הכנסת מונצח בשילוט המצוי באתר.

המבנה שימש כבית כנסת עד פרעות תרפ"ט, ואז ננטש. לאחר מכן היה המבנה חלק מהכפר הערבי קאלוניה - כיום מבשרת ציון. בשנת 1961, עם התיישבותן של המשפחות הראשונות באזור מוצא תחתית, שופץ הבניין וחזר לשמש בית כנסת. בשנת 1973 בוצעו ליד בית הכנסת חפירות ארכאולוגיות, בהן התגלו שרידי יישוב מהתקופה הרומית - יישוב ששמו היה קולוניה (מושבה בלטינית), מקור השם של הכפר הערבי שהיה במקום.

בית הכנסת שוכן סמוך לבית ילין.