הנער רני, הסופר אבַּבֶּטֶן וטייס החלל קפיטן יוקי יוצאים למסע הרפתקאות לגילוי שבט יהודי המדבר האגדיים, יהודי חייבר. מצוידים במדחס החלל ובמדחס הזמן, טסים השלושה בחללית אל העבר ורואים את ארץ־ישראל וסביבותיה כפי שהיו לפני שנים רבות, בתקופות העליות הראשונות. השלושה פוגשים כמה מגיבורי תקופות אלה, שגם הם חיפשו אחר שבט הבדואים היהודים עזי הנפש, שלפי השמועה התגוררו במדבר חיג'אז בלב חצי האי ערב. המסע רב־התלאות והסכנות בקרב שבטי הבדואים הפראיים הִנו סיפור עלילה מרתק ומשעשע, המבוסס ברובו על מאורעות שהתרחשו באמת.
בעקבות יהודי המדבר הוא הספר השני בסדרת ספרי הרפתקאות מרתקות ומשעשעות לבני הנעורים. הספר הראשון בסדרת מסעות אבבטן וקפיטן יוקי הוא אוצר הבאר הראשונה.