כיאה למיתוס, גם בסיפורי עשרת השבטים האבודים יש גיבורים. אך הגיבורים אינם עיקרו של הסיפור. עלילותיהם נועדו לרתק את השומעים או הקוראים, ליצור מתח ואמפתיה, אך גם להעביר ערכים ומסרים. הגיבורים הבולטים ביותר של המיתוס הם אלדד הדני ודוד הראובני. הם מוצגים כמי שהגיעו, בדרך כל שהיא, מארצם של השבטים אל העם היהודי המפוזר בגלות. אלדד הדני, (המאה ה 9), שדמותו ומוצאו לוטים בערפל, נחשב בכל זאת כדמות היסטורית, אם כי סיפוריו בדיוניים בעיקרם. ההיסטוריון שלום בארון תיאר אותו כ"מספר סיפורים נודד" אלדד מציג עצמו כבן שבט דן שיצא מארצו כדי "להגיד לכל בני ישראל המפוזרים בגולה ענייניו ועניין ארצנו לבשר אותם נחמות ולדבר על לבם דברים טובים" מסעותיו של אלדד בין ארצות השבטים רצופים בעלילות מסמרות שיער, הכוללות הפלגה בים סוער ושבי בידי שבט של אוכלי אדם שכמעט שאכלוהו חי. סערות בים ומפגש עם קניבלים הם מוטיבים שחוזרים במיתוסים ובסיפורי נוסעים בעת העתיקה ובימי הביניים. אלדד נחלץ מהסכנות לאו דווקא הודות לגבורתו או תושייתו אלא בזכות עזרת האל.
גיבור נודע אחר, דוד הראובני, (1490 בערך – 1538) שמוצאו ואישיותו עדיין לא מפוענחים, מופיע באירופה בתקופה הקשה שלאחר גירוש ספרד ובזמן שאימת האינקוויזיציה מרחפת על יהודים ואנוסים. בשונה מאלדד הדני, הראובני הוא הגיבור של סיפורו. לאחר שהציג את עצמו כנצר לשושלת דוד ובנו של מלך המולך על השבטים במדבר חיבר, הוא בא להציע למלכים באירופה ולאפיפיור את עזרת צבאות השבטים כדי להילחם במוסלמים ולשחרר את ירושלים. הראובני היה דמות היסטורית, ועלילותיו מתרחשות בתוך מרחב גאוגרפי והיסטורי ריאלי. בסיפוריו, שחלקם בוודאי בדיוניים, הוא מתאר שפע תהפוכות, אירועים ותיסבוכות שקרו לו במסעותיו בין חצר הוותיקאן ברומא וחצרות מלכים ונסיכים באירופה. הוא נכנס לצרות ואף נחלץ מהם, וממשיך בנחישות לפעול כדי להגשים את "שליחותו". למרות כישלונו וסופו הטראגי סיפורו צורף לאתוס הלאומי של משיחיות וכיסופי גאולה.
במשך השנים נוספו למיתוס סיפורי גבורה על שליחים שיצאו לחפש את השבטים האבודים כדי לבקש עזרה לקהילות הנתונות במצוקה. אחד הסיפורים הנודעים מימי הביניים בגרמניה מספר על ר' מאיר, מחבר הפיוט אקדמות מלין, שעבר את הסמבטיון כדי להביא עזרה לקהילתו שמאיים עליה צורר אכזר. בסיפור זה יש שני גיבורים: ר' מאיר שיצא למסע המסוכן, והגיבור מהיהודים האדומיםשהגיע מארצות השבטים. על פי אחת הנוסחאות לסיפור זה ה"גיבור" מהשבטים היה איש קטן וחיגר, שרק בזכות חוכמתו ועזרת האל ניצח את הצורר.
סיפור נפוץ אחר היה סיפור משנת 1646 על השליח ר' ברוך גד מירושלים שהלך לערי פרס ומדי. בשובו סיפר על ההרפתקאות שעבר בדרך, כיצד נפל בידי שודדים, וכיצד הציל אותו "גיבור חיל, קומתו גבוה מאוד ורומח בידו...והוא מבני שבט נפתלי ושמו מלכיאל". אותו מלכיאל נתן בידיו איגרת מאת "המלך אחיטוב בן עזריה, הנשיא יהוצדק בן עוזא והזקן אוריאל בן אביסף" משבט בני משה ובה דברי עידוד ליושבי הגלות וסיפורים על חירותם של עשרת השבטים. נוסח איגרת זו נשלח על ידי רבני ירושלים ונפוץ בדפוס בקהילות רבות.
במאה ה19 נפוצו סיפורים על מסעות של שד"רים ונוסעים שיצאו לחפש את השבטים במדבר ערב או בהרי איראן. אופייני למדי הוא הסיפור על השד"ר שיצא לתימן ופגש שם אדם משבט דן. הוא מתאר אותו בצבעוניות מיוחדת: "הדני הוא יפה תיאר ויפה מראה כביר כח ורב קומה, עיניו מפיקות אש אהבים זקנו יורד על פי גדותיו וקוצותיו ארוכות שחורות כעורב, יורדות על צוארו ועל גבו, בגדיו דומים לבגדי בני קדם, אך ממעל להם יחגור חגורה ארוכה ורחבת ידיים ועליה שזורים בכתב ולשון עברי אמרי קודש אלה "יהי דן נחש עלי דרך שפיפון עלי ארח" ועל ירכו מצומדת חרב גדולה ורחבה, לשונו הוא לשון עברית צחה, אך דבריו מעטים ובטרם יוציא הגה מפיו יחשוב מחשבות רגעים אחדים, מאכלו מעט מזער, ורק לחם ומים ושנתו שתים או שלש שעות מעת לעת פעמים רבות ביום הוא עמוק במחשבותיו ועיניו דלו למרום וכל רואהו אז במעמד הזה יאמין כי הוא דובר עם מלאכו ההולך אתו הליכות חלדו, רבות פעמים ביום הוא רוחץ בשרו במים, וכל תהלוכותיו ומעשיו נדמו לתהלוכות בני הנזירים נקובים בשם "איסים"... סיפורים דומים, המפליגים בהרפתקאות השליחים ובעלילות הגבורה שלהם היו פופולריים מאוד בקהילות רבות כמעט עד המאה ה-20.
מקום מושבם של השבטים האבודים.
המיתוס של עשרת השבטים נולד מתוך תעלומה: לאן נעלמו עשרת שבטי ישראל שהיו רוב התושבים בממלכת ישראל והוגלו על ידי שלמנאסר מלך אשור בשנת 722 לפנה"ס. חכמי המשנה והתלמוד, מאות שנים אחר כך, ניסו לזהות את המקומות שאליהם הוגלו השבטים אך נראה שלא הייתה להם ממש ידיעה היכן הם נמצאים ולא ידעו מה עלה בגורלם. הם דנים בשאלה אם השבטים האבודים יזכו לגאולה ויחזרו לארץ ישראל, אך באשר למקומם הם משתמשים בביטוי "ארץ אחרת" רמז לאגדות שהחלו להרקם סביב מקום השבטים אפשר למצוא במאמר של התלמוד: "לשלש גלויות גלו ישראל אחת לפנים מנהר סנבטיון ואחד לדפני של אנטיוכיה ואחד שירד עליהם הענן וכיסה אותם" ( ובגרסה אחרת: הרי החושך). באמירה זו כבר מהדהדות מסורות המסבירות שהשבטים ממשיכים להתקיים בארץ רחוקה אך אינם יכולים לצאת ממנה ואי אפשר להגיע אליהם בגלל מכשולים בלתי עבירים כמו הרים גבוהים או נהרות אדירים. המכשול העיקרי הוא נהר הסמבטיון, (או הסנבטיון, מהמילה: שבת). נהר מופלא המפסיק את זרימתו ביום השבת נזכר כבר במאה הראשונה לספירה על ידי חוקר הטבע הרומי פליניוס הזקן ועל ידי יוסף בן מתתיהו. המכשול השני הוא הרי החושך, הנזכרים בתלמוד כמכשול שאי אפשר לעוברו באגדה על אלכסנדר מוקדון
מקום מושבם של השבטים תואר כארץ רחוקה בקצה העולם, אך היא נמצאת ליד ארץ או ציון גאוגרפי שהיו ידועים ומוכרים כחלק מתמונת העולם של בני התקופה. ההנחה המקובלת עד לסוף ימי הביניים הייתה שמעבר לעולם הידוע יש עוד ארצות. ארצות אלה אמנם קיימות במציאות, אך יש בהן דברים מופלאים כמו חיות מוזרות ואפילו מפלצות, וגם בני אדם משונים או מסוכנים, שנוסעים נועזים היו מספרים עליהן סיפורי מדהימים. סיפורי אלדד הדני שנפוצו החל מהמאה התשיעית מיקמו את השבטים באזורים שונים בשולי העולם הידוע. ארבעה שבטים: דן, נפתלי, אשר וגד "נמצאים בארץ כוש עד היום הזה. הם חונים בחוילה הר הקדם אשר שם הזהב" את כוש וחוילה, הנזכרות במקרא נהוג היה לזהות עם סודאן ואתיופיה ואלדד מציין שהן שוכנות דרומית למצרים. הזיהוי של אתיופיה כארץ השבטים התקיים במשך מאות שנים, והושפע ככל הנראה משמועות על קיומה של הממלכה הנוצרית שהייתה באתיופיה, שנפוצו עם הסיפורים על פרסטר ג'ון ואולי גם משמועות על קהילת ביתא ישראל. עם זאת היו שזיהו את ארץ כוש עם הודו. ומיקמו אותה בפאתי מזרח אסיה ולא באפריקה. שבטים אחרים: שבט יששכר, שבט זבולון, שבט ראובן, שבט שמעון וחצי המנשה, מיקם אלדד צפונית-מזרחית למסופוטמיה. הוא מזכיר את נהר הפרת ואת פרס ומדי, את ארמניה,את ארץ כשדים, (ובנוסח אחר: את ארץ הכוזרים) כמקום מושבם. את שבט אפרים והחצי השני של שבט המנשה הוא ממקם "בהררי נגד מדינת מכה (או מאחה) ובכך פותח מסורת שמיקמה את השבטים במדבריות ערב. כך דוד הראובני במאה ה 16 הציג את עצמו כמי שבא מממלכה עצמאית של השבטים במדבר חבור, זיהוי שהתקשר עם שמועות על יהדותה של מלכות חמיר ועל היהודים בח'ייבר. התסיסה המשיחית סביב הופעתו של שבתאי צבי במאה ה 17 לוותה בשמועות על הופעתם של עשרת השבטים במקומות שונים בין מדבר פרס ומדבר ערב.
הסיפורים שנפוצו בימי הביניים, וגם אחריהם, על מקומם של השבטים לא היו ממש מחויבים למציאות גאוגרפית ריאלית. גם נהר הסמבטיון והררי החושך, המכשולים האגדיים שמונעים את הקשר עם השבטים, תוארו כנמצאים במקומות שונים, בהתאם לסיפור. במסורות נוצריות שנפוצו בימי הביניים זוהו עשרת השבטים עם גוג ומגוג, שתוארו באגדות אלו כשבטים פראיים שהם אויבי הנצרות, הנצורים מאחורי הרי הקווקז. במפות מימי הביניים ואפילו מהמאה ה-17, המתארות את העולם, הם מוקמו בשולי העולם שהיה ידוע אז, אך במקומות שונים: במזרח, בצפון, ועוד.
התגליות הגדולות בראשית העת החדשה פתחו אפשרויות חדשות למיקומם של השבטים. הרב והמדינאי מנשה בן ישראל האמין שהילידים ביבשת אמריקה הם צאצאי השבטים וספרו "מקוה ישראל" בו הציג את טענותיו זכה לתפוצה רבה בין יהודים ונוצרים. במאה ה-19 כשהתחזקו הקשרים בין המרכזים היהודיים ובין קהילות ישראל נידחות יותר, היו בהן מי שטענו שיש להם מסורות עתיקות על כך שהם מצאצאי עשרת השבטים, כמו יהודי אפגניסטן, בוכרה, הקווקז, כורדיסטן, וגיאורגיה. פרסום הידיעות על קהילות קאיפנג בסין וקוצ'ין בהודו עורר אף הוא השערות על מוצאן מהשבטים האבודים. במאה ה-20 התרחב החיפוש אחר צאצאי השבטים ונמצאו שבטי ילידים באפריקה ובגבול הודו, כמו בני המנשה, ממדינת מיזורם שבצפון מזרח הודו, שנודע שהם מקיימים מנהגים הדומים למנהגי היהדות
השבטים האבודים והגאולה.