Story in poem form - set in India or Arabia

I read this a few years ago and have always wished I wrote down the author and title. It's a story in story format - there's the frame story and then I think there were four stories told by one of the characters. The main story was about a girl journeying to meet and marry a prince and one of the people in the caravan tells her these stories, and then at the end turns out to be the prince. Set in India or Arabia, someplace like that. The copy I read was a small red hardback.
Thanks for any help!

try Thomas Moore's Lallah Rookh.

Touchstone fairy: Lallah Rookh

Ooh I think that's it! Thank you so much!!