מלכת שבא שמעה את שמע שלמה ובאה לירושלים לנסותו בחידות. חידותיה מגלות מה יש בלבבה: "וַתָּבוֹא לְנַסּוֹת אֶת שְׁלֹמֹה בְחִידוֹת… וַתְּדַבֵּר עִמּוֹ אֵת כָּל אֲשֶׁר הָיָה עִם לְבָבָהּ" (דברי הימים ב ט', א). כאשר המילה "חידה" עולה, אנו מיד נזכרים בשמשון ודלילה, וכפי שאומר רש"י: "בחידות - כמו: 'אחודה נא לכם חידה' דשמשון". חידות שמשון היו בזמן נישואיו לדלילה - אישה שאינה מאומתו. חלק מחידותיה של מלכת שבא מופיעות בתרגום לארמית של מגילת אסתר. גם סיפור מגילת אסתר דומה לסיפור שלנו - מלך שמתחתן עם מישהי שאיננה מאומתו. ואפשר שיש כאן רמז לקישור אינטימי בין מלכת שבא לשלמה המלך, העולה גם מן החידות עצמן.
הבה נקרא כמה מדברי המדרשים הללו על חידותיה של מלכת שבא לשלמה: "מיהם שלושה שלא אכלו ולא שתו והצילו שלוש נפשות? ענה לה: שלושה שלא אכלו הם החותמת, והפתיל והמטה של יהודה, והם הצילו את תמר, פרץ וזרח". בחידה זו יש קריצה לשושלת המלוכה - מיהודה, דרך פרץ עד לשלמה המלך, שושלת שראשיתה בקשר שלא היה נראה אידיאלי - בין יהודה לתמר. ועוד חדה לפניו: "הרי לך צורות (אנשים מכוסים בגלימה), בחר לי מהם איזה נקבה ואיזה זכר? בדקם בהילוכם, זכר מקדים ימין לשמאל, נקבה מקדימה שמאל לימין. ועוד: מהי חדר ועשרה דלתות, כשאחד נפתח - תשעה נסגרים, וכשתשעה פתוחים - אחד סגור? אמר לה: חדר - זה רחם של אישה, ועשרה דלתות - זה בן אדם שיש בו עשרה נקבים, כשהוולד נמצא במעי אימו - טבורו פתוח ושאר נקביו סגורים, וכשיוצא - טבורו נסגר ושאר נקביו נפתחים. ועוד אמרה לו: מהו שבעה יוצאים ותשעה נכנסים, שנים מוזגים ואחד שותה? אמר לה: שבעה ימי נידה - יוצאים, ותשעה ירחי לידה - נכנסים. שני דדי אישה מוזגים, ואחד שותה - זה הוולד. ועוד חדה לפניו: אשה אמרה לבנה: אביך - אבי, זקנך - בעלי, אתה - בני, ואני - אחותך. מי אני? אמרה לו: בוודאי ביתו של לוט שאמרה לבנו כן". שלמה המלך גם הוא צאצא של ביתו של לוט (שהרי הוא צאצא של רות המואבייה), ואשתו היא נעמה העמונית (מבני לוט).
כאמור, אפשר שמלכת שבא ניסתה בכל חידותיה אלה להכשיר את האווירה לקשר אינטימי בינה לבין שלמה. ואכן, יש מסורת אתיופית שמלכת שבא ילדה בן לשלמה ששמו מנליק, ושושלת ארוכה שלו מצויה עד היום באתיופיה. עוד מסופר, שנציגים של שנים עשר השבטים נשלחו עם מנליק לאתיופיה והם שמהווים את הגרעין של הזהות היהודית של יהודי אתיופיה. איך שלא יהיה, מפרקנו עולה כי שלמה המלך וחכמתו מביאים כבוד ומפיצים את שמעו עד למרחוק.