סיפור יהושע בן נון מובא בספר חבור יפה מהישועה לרבנו נסים גאון (הוצאה ראשונה פירארה שי״ז) ומביאו המקובל ר׳ נתן נטע בשם מדרש, הטעם שנקרא יהושע בן נון, והמרגלים קראו אותו דין ריש קטיעא (עי' סוטה ל״ה. ריש קטיעא ימלל, ופירש״י מי שראשו קטוע שאין לו בנים ליטול חלק בארץ, והערוך ע׳ רש פי' להכי קרו ליה קטיע לפי שהוסיף לו משה אות יו״ד שהיא קטיעא.), שאביו של יהושע דר במצרים ואשתו עקרה, והיה הצדיק מתפלל לנכח אשתו ויעתר לו ה׳. ויהי כי הרתה היה הצדיק מתענה ובוכה יום ולילה מאין הפוגות, וירע הדבר בעיני אשתו ותאמר לו היה לך לשמוח כי שמע ה׳ את תפלתך ולא ענה אותה, ויהי כדברה אליו יום ויום ותאלצהו בדבריה, ויגד לה את כל לבו, כי הגידו לו משמי מרום כי הבן הזה הנולד לו יתי את ראשו והאמינה לדבריו, כי ידעה כי כל דבריו באמונה. ויהי כאשר ילדה והנה הוא בן, ותקח לו אמו תיבה ותחמרה בחמר ובזפת ותשם בה את הילד ותשלך אותו בתוך היאור, וימן ה' דג גדול לבלוע אה התיבה, ויהי היום ויעש המלך משתה לכל שריו ועבדיו, וילכוד את הדג שבלע התבה ויביאהו לפני המלך, וישסעהו והנה נער בוכה, ויתמה המלך וכל שריו, ויאמר המלך להביא אשה להניק את הילד, ויגדל הנער בבית המלך ויפקד אותו להיות סנדטור (תליון, שר הטבחים). ויהי אחר הדברים האלה חטא אותו הצדיק אביו יהושע למלך מצרים ויצו המלך להסנדטור לחתוך את ראשו וליקח את אשתו ובניו ורכושו לעצמו כמשפטם בעת ההיא, ויהי כאשר קרב אל אמו לבוא עליה, אז נתמלא כל המטה חלב מדדיה, ויחרד חרדה גדולת מאד ויטול את חניתו להרגה באמרו כי מכשפה היא, ותזכור אמו את דברי אביו הצדיק ז״ל, אף היא תשיב אמריה לו, אין זה כשוף כי אם חלב שהניקו אותך מפני שאני אמך, וספרה לו כל המאורע, מיד בדל עצמו ממנה, כי גם הוא נזכר שמועתו שנמצא בדג, אפס לא ידע כי היה אביו ועשה תשובה, ולכן קראו אותו בן נון מפני שנמצא בדג ובלשון ארמי נון, וריש קטיעא קראו אותו המרגלים על שם מעשיו הראשונים מה שעשה לאביו עכ״ל (עי' הקדמה לרב פעלים צד 23).
מלבד ספר יהושע בתנ״ך נמצא ספר יהושע בן נון או יושע בן נון להשמרונים או הכותיים שאין להם ספרי נביאים וכתובים רק ספר יהושע לבד בנוסחא משונה בלשון ערבית עם העתקה עברית (עי׳ כרמי שמרון צד 55 והלאה) ועוד העתקה עברית בנוסחא אחרת (עי' ירושלם של לונץ ח״ו 138) וכ״י שהו״ל ר״מ גאסטר אשר לדעתו מקורו עברית (ע״ע יהושע באוצר ישראל). גם יש להם אגרת של יהושע שכתב למלכי פרס ונדפסה בכרמי שמרון (צד 69), ובנוסחא אחרת בספר היוחסין השלם (לונדון תרי״ז). אך ידוע הוא שאין לסמוך על השמרונים כי היו מזייפים התורה כדי לחזק אמונתם בהר גריזים, וחברו ספרים כוזבים.