大雄等人用「進入故事鞋」到天方夜譚的故事中遊玩,當旅遊結束回到家中,發現靜香仍在故事書中的世界,而遊戲用的故事書居然被媽媽燒掉了。正在憂慮之際,大雄等人想起《天方夜譚》中也有真實的人物啊!或許故事書中的世界與現實世界也有關聯性!失去入口的哆啦A夢等人,搭乘時光機與時光旅行社的導遊米庫金一起回到過去的巴格達找尋靜香。可是,他們一到古代就被四十大盜的首領卡斯姆盯上,哆啦A夢遺失了重要的百寶袋,四人居然還在乘船航行的途中被拋下海!
好不容易度過難關,大雄等人遇上了黃金宮殿的辛巴達--也就是《天方夜譚》裡的辛巴達。在辛巴達的協助下,他們順利從奴隸商人阿普西手中救出了靜香。雖然旅行的目的達成了,但是卡斯姆與阿普西都對黃金宮殿存有遐想,打算大肆洗劫、支配世界。辛巴達是個老國王,已經失去了年輕時代的聰明幹練,大雄見狀十分生氣,教訓了他一頓。辛巴達皤然醒悟,終於與想來奪取黃金宮殿的壞人決一死戰。