青い眼を持つアズールと黒い瞳を持つアスマール。アラビア人の乳母ジェナヌのもと、アズールはヨーロッパの領主の子、アスマールは貧しい他国者の乳母の子と身分の違いはあっても、ふたりはおやつもお乳も子守唄も半分ずつ。まるで兄弟のように暮らしていた。しかし身分も人種も違えば、生活は異なってくる。立派な服を着て、剣道に乗馬にダンスにと忙しいアズールに対して、それを見ているだけのアスマール。お互いの違いがケンカの種になるのもしょっちゅうだったが、困った時は助け合う本当は仲の良いふたり……しかし別れは突然やってきた。アズールが寄宿生活をすることになり、領主はジェナヌとアスマールを屋敷から追い出してしまう。時は流れたが、成長したアズールはジェナヌの唄っていた子守唄を忘れることができない。その歌に出てくる「ジンの妖精」を救うため、海を渡ることを決意する。辿り着いた憧れの国で最初に耳にした言葉は「青い眼は不吉」。遠いイスラムの地で仕方なく盲目のふりをして暮らすアズールだったが、旅の途中、聞き覚えのある声を耳にする。すぐにジェナヌだとわかるも、商売で成功し、大富豪になっていたジェナヌは、物乞い同然の青年をアズールだとは気付かない。そこでアズールは、幼い頃にジェナヌに聞いた子守唄をアラビア語で唄ってみせる。ジェナヌもアズールと気付き、再会に涙を流す二人。そこへアスマールが帰ってくる。彼は「ジンの妖精」を救うため、明日旅立つという。自分も行きたいと名乗り出るアズールだが、アスマールは過去の恨みから別々に旅をすることを主張する。ひとまず一緒に行動することになったが、しかし度重なる危険の中で、アスマールは兄弟のように仲が良かったころの感情を取り戻していく。旅の果て、彼らは2つの門へ辿り着く。どちらが「ジンの妖精」のいる場所へと続いているのか、そしてアズールとアスマールはどういう選択をするのであろうか。