He set out to find the hoopoe bird, which could detect water under the ground. He sent signals all over for the hoopoe to call on him, but it was nowhere to be found. In anger, he declared that unless the bird had good reason for its absence, he would punish it severely.
The hoopoe eventually came to Solomon and explained the reason for its delay: "I have discovered something of which you are not aware. I have come from Sheba (Saba) with important news. Solomon became curious, and his anger subsided. The bird continued: "Saba is ruled by a queen named Bilkis (Bilqis), who has plenty of everything, including a splendid throne. But in spite of all this wealth, Satan has entered her heart and the hearts of her people. She rules their minds completely. I was shocked to learn that they worship the sun instead of Allah the Almighty."
To check the hoopoe's information, Solomon sent a letter to the queen with the bird. He instructed the bird to remain hidden and to watch everything.