Большую часть фильма два главных персонажа, Алитея и Джинн, сидят в номере стамбульского отеля (в том самом, где Агата Кристи написала «Убийство в Восточном экспрессе»!), закутавшись в уютные банные халаты, и говорят о любви, судьбе, силе историй и стремлении к свободе. Разговоры эти перемежаются экскурсами в прошлое Джинна, поданными в виде роскошных ярких флешбэков. Современный мир в фильме сжат до небольших прозаических локаций: гостиничного номера, вагона метро, заднего двора, полупустого парка. Даже когда в начале фильма Алитея попадает в зал, полный людей, их лица словно размыты и почти сливаются с окружающим фоном. Зато прошлое в рассказах Джинна блещет яркими красками, колоритными персонажами и пропитано волшебной атмосферой Ближнего Востока.
«Три тысячи лет желаний» — фильм о любви и силе её последствий. Джинн рассказывает Алитее три истории из своего прошлого, одна из которых произошла во времена библейского царя Соломона, другая — в эпоху правления султана Сулеймана, а третья — в XIX веке. Все эти истории объединяет одно — Джинн оказывается заточён в сосуде из-за любви, своей или чужой. Ещё это истории о свободе и неволе. Джинн дважды попал в заточение, пытаясь защитить тех, кто ему дорог. Но в третий раз он угодил в бутылку из-за того, что испугался свободы и решил обменять её на жизнь в клетке с возлюбленной.