סיפור הרקע שבחר רבי יהודה הלוי לספרו הכוזרי (1139) הוא סיפורו של "מֶלֶךְ כּוּזָר הַנִּכְנַס בְּדַת הַיְּהוּדִים הַיּום כְּאַרְבַּע מֵאות שנה". המלך, שרבי יהודה הלוי אינו נוקב בשמו, הגיע אל האמונה באמצעות מלאך שהתגלה אליו בחלום, כמו בסיפור ההתגיירות שבמכתב המלך יוסף. סיפור הוויכוח בין חכם יהודי וחכמי הנצרות והאסלאם שמתואר במכתב יוסף הוא המסד לדיון התאולוגי בספר הכוזרי. רבי יהודה הלוי אינו מזכיר את המכתב אך מציין שהסיפור "נזכר ונודע בספרי דברי הימים", מכאן שהסיפור או המכתב היה ידוע בימיו.
מקור יהודי נוסף שמזכיר את סיפור ההתגיירות ואת ההתכתבות הוא ספר הקבלה שנכתב על ידי הראב"ד, רבי אברהם אבן דאוד (1110–1180). הוא מזכיר את מכתב יוסף המלך ואת הכוזרים כיהודים רבניים (שאינם קראים) ואומר: "שהיו שם עמים כוזריים שהתגיירו ויוסף מלכם שלח ספר לר' חסדאי הנשיא בר' יצחק בר שפרוט והודיעו שהוא על דעת רבנות וכל עמו וראינו בטוליטולה מבני בניהם תלמידי חכמים והודיעונו שאריתם על דעת רבנות". "ספר הקבלה" חובר כנראה בשנת 1160 בקירוב. כלומר, כ-200 שנה לאחר זמנו של חסדאי.
הנוסח הראשון הידוע של המכתב ששלח חסדאי אבן שפרוט ליוסף מלך הכוזרים ומכתב התשובה של המלך הופיע לראשונה בספרו של יצחק עקריש "קול המבשר" שנדפס בקושטא בשנת 1577. ספרו של עקריש חזר ופורסם מאז כחלק מקבצים שונים. בשנת 1600 צירף המלומד הקלוויניסט יוהאן בוקסטורף את חליפת המכתבים שפרסם עקריש לתרגום ללטינית של ספר "הכוזרי". המכתבים חוזרים ומצורפים מאז כהקדמה במהדורות של ספר הכוזרי בעברית. כתב יד של שני המכתבים בנוסח זהה, כנראה מן המאה ה-16, שמור באוקספורד.
בשנת 1879 פרסם אברהם הרכבי נוסח של מכתב המלך יוסף שהגיע לידיו של החוקר והאספן הקראי אברהם פירקוביץ', כנראה מגניזת קהיר. נוסח זה דומה מאוד בתכניו לזה שפרסם עקריש, אך ארוך יותר ושונה במספר פרטים, בעיקר לשוניים וסגנוניים. המסמך נמצא בתוך קובץ של כתבי יד בנושאים שונים, לפי השערה מן המאה ה-13, ונמסר לספריה הלאומית בסנקט פטרבורג כחלק מאוסף פירקוביץ' השני.
ב-1912 פרסם שניאור זלמן שכטר מסמך שמצא בגניזה הקהירית. שכטר העריך כי המכתב הוא מהמאה ה-12 או מוקדם יותר והסיק מתוכנו כי הכותב האנונימי הוא נתין של המלך הכוזרי יוסף והנמען הוא חסדאי אבן שפרוט. בדומה למכתב יוסף שפרסם עקריש גם הכותב במסמך זה מספר על התגיירות הכוזרים, ומתאר את ארצם. המכתב נתרם על ידי שכטר לספריה באוניברסיטת קיימברידג' יחד עם שאר מסמכי הגניזה. המכתב, הידוע גם כ"מכתב שכטר" או "מסמך קיימברידג'", עורר עניין רב בקרב ההיסטוריונים וחידש ביתר שאת את הדיון על אותנטיות ההתכתבות הכוזרית ומהימנות סיפור ההתגיירות.
סיפור ההתגיירות באיגרת חסדאי אבן שפרוט אל יוסף מלך הכוזרים.
איגרת חסדאי אבן שפרוט אל יוסף מלך הכוזרים היא חלק מחליפת מכתבים בין יוסף, מלך הכוזרים לחסדאי אבן שפרוט.
באיגרת פונה חסדאי אל מלך כזריה ומבקש פרטים על ממלכתו ועל התגיירות הכוזרים.
חסדאי מספר במכתב שתמיד שאל את שלוחי הארצות המגיעים לספרד על מצבם של בני עמו. סוחרים מח'וראסאן סיפרו לו "כי יש ממלכת ליהודים נקראים על שם אל-כזר", על המרחק בינה ובין ביזנטיון ("אלקושטנטניה") על המלך יוסף ועל קשרי המסחר בין ארצם ובין ממלכת הכוזרים. חסדאי, שנדהם והתמלא שמחה לשמע הדברים, שלח שליח בשם יצחק בר נתן עם איגרת ומתנות למלך הכוזרים ולקיסר ביזנץ. הקיסר עיכב את השליח במשך ששה חדשים ושלחו בחזרה בטענה כי בינו ובין ממלכת הכוזרים יש מלחמות וים סוער. חסדאי שב ושולח שני שליחים ומביע תקווה שאיגרת זו, שנתן בידיהם, תגיע למלך. הוא מבקש מהמלך שיצווה על הסופרים שיכתבו לו תשובה שלמה ומבטיח כי אם השמועות על הממלכה היהודית תתאמתנה, הוא יעזוב את משרתו הרמה ויצא לדרך הארוכה אל ממלכת הכוזרים.
על אף שנדהם לשמוע על הממלכה היהודית, והוא שואל את המלך "איך הייתה נפילת ישראל במקום ההוא", נראה מן המשך כי יש דברים הידועים לו: "ואבותינו ספרו לנו" כי המקום נקרא הר שעיר ובגלל גזרות הגיעו לשם ו"ישישי דור קדמוני" סיפרו על גזירת שמד שבעטיה גנזו במערה ספרי תורה וספרי קודש והיו מתפללים במערה ולמדו את בניהם להתפלל עד שברבות הימים שכחו את המערה ואת התפילות.
בהמשך איגרתו פונה חסדאי אל המלך בשאלות רבות: מאיזה שבט הוא? מי הם מלכי הארץ ומהם נוהגי הורשת המלוכה? מהו שטחה של ארצו ומהם גבולותיה? האם היא גשומה או מושקה? מה גודל צבאה ועל כמה מדינות היא שולטת? עם אילו עמים הוא נלחם? באיזו שפה מדברים בארצו? והאם המלחמה דוחה שבת? ו"אם יש אצלכם זכר לחשבון קץ הפלאות אשר אנו מחכים זה כמה שנים".
נראה שהאגרות היו קיימות כבר במאה ה-11, שכן רבי יהודה בן ברזילי הברצלוני מתייחס אליהן בספר שמתוארך בין השנים 1090 ו-1105. הוא מפקפק באמינותן וחושש כי הן זיוף, וכותב "לא ידעתי אם אמת היה הדבר שנתגיירו הכוזרים שהם מבני תוגרמה או לא". מקור יהודי נוסף שמזכיר את סיפור ההתגיירות ואת ההתכתבות הוא ספר הקבלה שנכתב על ידי אברהם אבן דאוד.
מכתב חסדאי ותשובת המלך יוסף פורסמו לראשונה רק בדפוס ב-1577 בידי יצחק עקריש בקובץ "קול המבשר". בין החוקרים יש הסבורים שגם איגרת חסדאי וגם תשובת המלך הכוזרי נכתבו בידי מנחם בן סרוק מזכירו של חסדאי. חוקרים אחרים מטילים ספק באותנטיות של המכתבים ומניחים שהם יצירה ספרותית פסבדואפיגרפית.
האיגרת כתובה בסגנון האופייני למכתבים דיפלומטיים בתקופה. ראשיתו בהקדמה של אקרוסטיכון מחורז של 25 השורות הראשונות היוצר את שמו המלא של הכותב: "אני חסדאי בר יצחק בר עזרא שפרוט". החוקרים משערים שהקדמה זו, ונראה שגם המכתב כולו נכתבו על ידי מזכירו של חסדאי, מנחם בן סרוק.
סיפור ההתגיירות במכתב יוסף מלך הכוזרים אל חסדאי אבן שפרוט.
שני הנוסחים הידועים של המכתב, הנוסח שפורסם על ידי עקריש ב"קול המבשר" והנוסח של פירקוביץ', כמעט זהים בתוכנם, אך יש ביניהם שינויי סגנון ושפה רבים. נוסח פירקוביץ' ארוך מעט יותר מנוסח עקריש, אך הסיומת בנוסח עקריש, המתייחסת לשאלתו של חסדאי בדבר הציפייה לגאולה והבעת תקווה לפגישה עם חסדאי, חסרה בנוסח פירקוביץ'.
המכתב נפתח בדברי שבח מקובלים בכבודו של חסדאי ובהבעת שמחה על המכתב ששלח. הכותב מציין כי "כבר היו בין אבותינו דרישת שלום והדבר הזה שמור בספרינו ידוע לכל זקני ארצינו" הוא מזכיר את השאלות המופיעות במכתב חסדאי ועונה עליהן. לשאלה על מוצאם של הכוזרים עונה הכותב כי עמו הוא מצאצאי כזר, בנו השביעי של תוגרמה, בנו של יפת. אבות אבותיו נלחמו בתושבי הארץ הקודמים וגרשו אותם. אחרי דורות, לפי נוסח עקריש קם מלך חכם וירא אלוהים בשם בולאן מלאך ה' נראה אליו בחלום פעמיים והמלך וכל "שריו ועבדיו קיבלו את הדין ונכנסו תחת כנפי השכינה". הסיפור על מלך שמלאך מופיע בחלומו מופיע גם ב"ספר הכוזרי". המלאך שב וביקש מהמלך שיבנה לאלוהים משכן. המלך טען שאינו יכול כי אין לו כסף וזהב. המלאך הורה לו לצאת למלחמה והבטיח שינצח בה וימצא "שני אוצרות, אחד של כסף ואחד של זהב", וכך היה. בעזרת הממון הזה בנה המלך "אוהל וארון ומנורה ושולחן ומזבחות וכלי הקודש", ואלה קיימים עד היום. גם בספר הכוזרי נזכרים מטמונים שכנראה באמצעותם בנו הכוזרים "בֵּית הַמִּקְדָּשׁ עַד שֶׁהֵקִימוּ תַבְנִית הַמִּשְׁכָּן אֲשֶׁר עָשָׂה משֶׁה".
אחרי התגיירות המלך ועמו ניסו מלכי הנוצרים והמוסלמים לשכנע את הכוזרים לחזור בהם. הם שלחו את חכמיהם ובוויכוח שהתקיים ביניהם ובין חכם יהודי ניצח החכם היהודי. בעקבות הניצחון נימולו המלך ועבדיו והמלך קרא לחכמים שיבואו ויפרשו לו את התורה והמצוות. אחד מבני בניו של בולאן, מלך בשם עובדיה, "חידש את המלוכה וחזק את הדין כראוי וכהלכה. והוא בנה את בתי כנסיות ובתי מדרשות. והוא קבץ את חכמי ישראל ונתן להם כסף וזהב ופרשו כ"ד ספרים ומשנה ותלמוד ומחזורות של חזנים"... אחרי המלך הזה קמה לכזריה שושלת מלכים מזרעו ולכולם שמות עבריים: חזקיה, מנשה, חנוכה, יצחק, זבולון, משה, נסי, אהרון, מנחם ובנימין. כותב המכתב, יוסף בן אהרון המלך, הוא "מלך בן מלך בן מבני מלכים ולא יוכל זר לשבת על כיסא אבותי".
סיפור ההתגיירות במכתב מהגניזה.
כתב היד שמצא סלומון שכטר בגניזה הקהירית, הידוע גם כמכתב שכטר או מסמך קיימברידג', מכיל אף הוא את סיפור התגיירות הכוזרים. בגלל מצבו הגרוע של המסמך חסרים בו חלקים, מספר קטעים אינם ברורים ונתונים לפרשנות וחסרים הפתיחה והסיום. שכטר העריך שהמסמך הוא מהמאה ה-12 או ה-11, אך יש חוקרים המקדימים אותו למאה ה-10. רוב החוקרים מניחים שהוא העתק של מכתב שנשלח מנתין של ממלכת כזריה אל חסדאי אבן שפרוט. הכותב מזכיר לנמען את "שלוחיך לקוסטנטינא", שעשויים להיות השליחים שחסדאי מזכיר במכתבו ליוסף. תוכן המכתב מתייחס לרוב השאלות שהציג חסדאי במכתבו: מוצא הכוזרים וההתגיירות, מקום ארצם, ויחסי ממלכתם עם העמים והמדינות השכנות. תיאור הארץ במסמך הגניזה מצומצם מאוד בהשוואה למכתב יוסף, אך תיאור היחסים עם השכנים והמלחמות עימם נרחב ומפורט יותר, וגם שונה בפרטים רבים.