העלייה מתימן הייתה התופעה המובהקת ביותר של 'קהילה מתחסלת'. קהילת תימן, מן העתיקות שבגלויות, קיימה קשרים הדוקים עם היישוב בארץ-ישראל במאות השנים האחרונות. ערב הקמת המדינה חיו בה כ-50,000 נפש, מפוזרים בעשרות כפרים, עיירות וערים. ממשלת תימן הזדהתה באורח קיצוני עם מאבק הערבים בתנועה הציונית בארץ-ישראל, וההיתר ליציאת היהודים שניתן בקיץ 1949 היה אפוא בגדר הפתעה רבתי.
בסוף 1948 הגיעו ארצה כ-5,000 עולים מתימן; אך אלה היו פליטים שיצאו מתימן עוד בשנת 1945, ונעצרו בעדן בדרכם ארצה. מחנה המעצר שלהם, 'חאשד' – בקרבת העיר עדן – כונה בפיהם מחנה 'גאולה'. הבריטים ששלטו במושבת הכתר עדן, לא הניחו בהתאם למדיניותם, לפליטים מתימן לעלות לישראל, הן קודם קום המדינה והן מיד לאחר היווסדה – כדי למנוע את תגבור הכוחות הלוחמים בארץ במלחמת העצמאות. אף כאשר ניתן ההיתר לעלייה בנובמבר 1948, עיכבו הבריטים את עלייתם של כ-800 צעירים בגיל גיוס. מאין קשר יבשתי עם עדן, אורגנה עלייתם של בני תימן ברכבת אווירית.
המטוס הראשון הגיע ללוד ב-16 בדצמבר 1948, עיתוי שהוסיף נופך לאווירה המיוחדת שנוצרה בארץ סביב העלייה מתימן: המטוסים חלפו בשמי הנגב בעת שבשדותיו ניטשו עוד קרבות בין צה"ל לכוחות המצריים. עלייתם של 5,250 פליטי תימן מעדן נמשכה עד 12 במארס 1949.
עם צאת אחרוני הפליטים ממחנה חאשד, החליטו הבריטים לנעול את שעריו ולפרקו, אולי מתוך מגמה מכוונת למנוע את המשך היציאה. יחסיהם של הבריטים עם שלטונות תימן היו מורכבים: הם חששו שפעולתם עשויה להתפרש כסיוע לעולים לישראל, אויבת העולם המוסלמי, ואף היו שמועות שהם מעודדים בסתר את האימאם של תימן למנוע את יציאת היהודים. על אנשי הג'וינט בעדן אסרו הבריטים לטפל בפליטים נוספים שיגיעו מתימן.
היהודים בתימן היו כפופים לשלוש רשויות: רובם הגדול חיו בתחומי מלכות האימאם; חלקם בשטחי הפרוטקטורט – אזור הסולטאנים שבין תימן לעדן; וחלקם בעדן – שהיתה מושבת כתר בריטית. שליחי העלייה, שהגיעו לעדן, חיפשו דרכים לחדור לריכוזי היהודים בתימן ולעודדם לעלות. בו בזמן נעשו מאמצים, באמצעות מתווכים, להניע את שליטי תימן להתיר את יציאת היהודים, או לפחות להעלים עין מיציאתם החשאית. במארס 1949 נלכדה קבוצת עולים, שיצאה בסתר לעדן, על הגבול, בלא שניתן לה להמשיך בדרכה. לאחר מאמצים רבים, שידולים והפצרות שהופנו אל הסולטאן, ומתת כסף נדיבה, הסכים הלה להניח להם לצאת – אך אז עצרו הבריטים את כניסתם לעדן; רק במגעים קדחתניים הושגה הסכמתם לכניסת היהודים לעדן – בתנאי שזו תהיה רק תחנת מעבר בדרכם ארצה, לשהות של שעות אחדות בלבד. זה היה הזרזיף הראשון של היציאה מתימן, שהפך לזרם גדול עם השגת הסכמתו של האימאם, במאי 1949, ליציאת היהודים מארצו. בכך החל למעשה המבצע הגדול של 'מרבד הקסמים', שיהודי תימן העדיפו לכנותו 'על כנפי נשרים', בלשון המקרא. במבצע זה הועלו ארצה רבבות יהודי תימן בתוך זמן קצר. החיפזון נבע מהחשש, שמא ישובו שליטי תימן וינעלו את שערי היציאה.
הבריטים, שהתירו לעולים לעבור דרך עדן, דרשו שיהודי תימן לא ייכנסו אל העיר עצמה אלא יוקם למענם מחנה מעבר מחוצה לה, בקרבת מחנה חאשד הראשון; הם נימקו זאת בחשש מפני מחלות מדבקות. גם המחנה השני כונה מחנה 'גאולה'. הוא הוקם לשש מאות עד אלף איש, ונועד לשהות קצרה ביותר. מרבית העולים שוכנו שם באוהלים, ובמחנה חסרו סידורי סניטאציה אלמנטאריים. הקמת המחנה, ניהולו ומימונו נעשו בידי הג'וינט. ביוני החלו באים למחנה זה ראשוני היוצאים מתימן.
ותוך שבועות אחדים החלו להגיע, בקצב הולך וגובר, השיירות הגדולות המאורגנות: תוך זמן קצר נתרכזו במחנה אלפי אנשים. מהלך היציאה מתימן היה קשה ומפרך; מעשרות קהילות ברחבי תימן, עשו היהודים את רוב המסע הארוך ברגל או על גבי חמורים. ההליכה המייגעת, פגיעות שודדי הדרכים, נחת זרועם של שליטים צמאי כסף וחמסנים והתנכלויות של האוכלוסייה העוינת – כל אלה רוששו אותם והתישו את כוחם. שליחי העלייה המעטים, שהצליחו לחדור לתימן, יכלו לסייע אך במעט, ורק כשהגיעו העולים לתחום לחג', בקרבת עדן, עזרו להם אנשי הג'וינט בארגון הסעתם למחנה 'גאולה'. לעתים מזומנות נעצרו השיירות בדרכן, לכודות על הגבול בין התימנים – שמהם ביקשו להימלט – לבין שלטונות עדן, שמנעו את כניסתם למחנה 'גאולה'. פעמים נשקפה סכנה לחייהם של אלפי הפליטים שנותרו ללא מזון, ובהם נשים, תינוקות וקשישים, חולים ותשושים. עם זאת הוסיפו יהודי תימן לעשות דרכם לעדן בואכה ישראל.
להנהלת הסוכנות ולמערכת הקליטה לא היתה שליטה על זרם היוצאים מתימן, ובחודשים הראשונים אף חסרו מידע מוסמך על מספר היהודים בתימן ועל גודל השיירות שנעו בדרך לארץ. המידע על היהודים שבמחנה 'גאולה' – מספרם, הרכב המשפחות ומצבם הרפואי – היה גם הוא מעורפל. פעילות השליחים הבודדים שהצליחו לחדור לתימן היתה מורכבת, מאחר שהיהודים היו מפוזרים במקומות רבים; ובהעדר אמצעי תקשורת, הגיעו ידיעות מקוטעות וחלקיות. החשאיות שאפפה את פעולתם מחשש השלטונות והאוכלוסייה העוינת מנעה מהשליחים אפשרות לשמור גם על קשר רצוף עם המוסדות בארץ; רוב הפעילות אולתרה במקום, לפי התנאים והמצבים המשתנים. המבצע של הוצאת היהודים מתימן נשמר בסוד כמוס מאמצעי התקשורת, כדי שלא לעורר את התנגדות התימנים וארצות האסלאם האחרות.