Nobita Nobi and Doraemon experience the tale of Sinbad the Sailor of the Arabian Nights fame firsthand using a storybook gadget, but Nobita becomes bored by just watching it from afar. He tries to invite Shizuka Minamoto to enter the storybooks of other tales and accidentally brings Takeshi "Gian" Goda and Suneo Honekawa along. Gian and Suneo mess up the storybooks to create a "fresh" tale, which causes Nobita and Shizuka to experience a mishmash of various tales that Shizuka dislikes. Attempting to leave, she is knocked out by Sinbad's magic carpet and falls into the desert.
The next day, Doraemon realizes that Shizuka has gone missing and stages a rescue mission by going to 8th century Baghdad, during the reign of caliph Harun al-Rashid, after receiving a confirmation from the future that the world of the Arabian Nights does indeed coincide with the 8th century Abbasid Caliphate. Posing as foreign traders and servants, Nobita, Doraemon, Gian, and Suneo are rescued from Cassim and his bandits by the caliph himself, who gives a permit that allows them to travel from the port of Basra. Initially, the four are accompanied by Mikujin, a guide genie, but the latter goes upset when they insult him due to his incompetency and leaves. After purchasing a ship, however, the group are double-crossed by the trader, who reveals himself to be Cassim, and are thrown overboard.
Waking up on the shore of the Arabian Desert, the four are forced to walk through it because Doraemon's pocket is lost during the storm that also crashed Cassim's ship. However, they are rescued by a gigantic genie commandeered by Sinbad, who reigns over a marvelous city in the desert presented by an anonymous time traveler from the future. With his magical gadgets, Sinbad helps the four rescue Shizuka from a bandit named Abdil. Vowing revenge, Abdil meets with Cassim and his two minions to search for the lost city. It is then revealed that Abdil was the only visitor to Sinbad's city who remembers its location, because when Sinbad urged him to drink a memory potion after the visit, he spewed it away.
After arriving, Abdil and Cassim swiftly take the city from Sinbad, whom they expel. Mikujin returns and helps the group with Doraemon's pocket, which he recovered after the storm. The group eventually manage to defeat Abdil and Cassim and retake the city. Despite Sinbad's offer for them to remain by not erasing their memories with the memory potion, Nobita and his friends bid him farewell before returning to the present day.
|Nobita Nobi||Noriko Ohara|
|Shizuka Minamoto||Michiko Nomura|
|Suneo Honekawa||Kaneta Kimotsuki|
|Takeshi Goda||Kazuya Tatekabe|
|Tamako Nobi||Sachiko Chijimatsu|
|Shizuka's mother||Masako Matsubara|
|Suneo's mother||Mari Yokoo|
|Sindbad the Sailor||Osamu Saka|
|Minions|| Reizo Nomoto|
|Harun al-Rashid||Jun Hazumi|
|Genie of the Lamp||Teiyu Ichiryusai|
|Genie of the Bottle||Daisuke Gouri|
|Young Sindbad||Hirohiko Kakegawa|
|Merchants|| Masayuki Sato|