فمن ذلك غزوته التي راسل فيها بلقيس- وهي فيما يقول أهل الأنساب- يلمقة ابنة اليشرح- ويقول بعضهم: ابنة إيلي شرح، ويقول بعضهم: ابنة ذي شرح- بن ذي جدن بن أيلي شرح بن الحارث بن قيس بن صيفي بن سبا ابن يشجب بن يعرب بن قحطان ثم صارت إليه سلما بغير حرب ولا قتال.
وكان سبب مراسلته إياها- فيما ذكر- أنه فقد الهدهد يوما في مسير كان يسيره، واحتاج إلى الماء فلم يعلم من حضره بعده، وقيل له علم ذلك عند الهدهد، فسأل عن الهدهد فلم يجده وقال بعضهم: بل إنما سأل سليمان عن الهدهد لإخلاله بالنبوة.