Patchy the Pirate finds himself in a frustrating traffic jam on US 101 near Encino, and he is understandably upset at the thought of missing out on the latest episode of SpongeBob SquarePants. His cell phone rings, and his parrot, Potty, urges him to hurry as the episode is about to start. Patchy, in a moment of desperation, requests Potty to record the episode, only to be met with the disappointing news that Potty had thrown the Betamax machine in the garbage. As the traffic begins to move, Patchy quickly realizes that Encino has mysteriously disappeared.
In a surreal moment, Patchy hallucinates encountering a man in an oversized SpongeBob costume claiming to be SpongeBob SquarePants. This SpongeBob figure assures Patchy that he will return to Encino if he just "believes." Moments later, he is jolted from this hallucination by Potty, only to find that Encino continues to elude him.
Following the special episode of SpongeBob, Patchy discovers Encino reduced to a miniature version. He encounters a family of aliens who reveal their son, Norbluck 5, has been using their shrink ray. Patchy, frustrated yet determined, insists that they restore the town to its original size, and they comply. After successfully returning to his home in Encino, Patchy faces a humorous twist of fate as he is crushed by a giant Potty the Parrot.
Elsewhere, SpongeBob and Patrick are engaged in the futile task of photographing the bubbles they have blown. In their attempts, they create a bubble large enough to float into a cave where they stumble upon a fragment of a medallion believed to lead to the lost city of Atlantis. Oblivious to its significance, they take the medallion piece to the Bikini Bottom Museum, where they encounter Squidward, who mistakenly thinks they have stolen the other half of the medallion. Realizing they hold the missing piece, Squidward informs them that it is the key to Atlantis, igniting SpongeBob and Patrick’s curiosity about the city's main attraction, the "World's Oldest Bubble."
Squidward carefully reassembles the medallion, which opens what they call the "path to Atlantis," a bus powered by "song fuel." They are soon joined by Mr. Krabs and Sandy Cheeks, embarking on an adventurous journey that results in an unplanned crash landing into Atlantis. However, unbeknownst to them, Plankton is stealthily pursuing his own agenda, eager to exploit the city's powerful weapons for his schemes.
Once in Atlantis, they meet the Atlantean Emperor, Lord Royal Highness, played by David Bowie, who graciously offers a lavish tour of the grand fortress. As they marvel at the sights, Mr. Krabs is drawn to the treasury room, Sandy to a science laboratory, and Squidward to an art gallery, each getting momentarily distracted. Meanwhile, Plankton sneaks into the armory vault and absconds with a tank.
SpongeBob and Patrick finally reach the world's oldest living bubble, but when Patrick takes a picture, it accidentally pops, leaving them horrified. As Mr. Krabs, Sandy, and Squidward recount their adventures to Lord Royal Highness, SpongeBob and Patrick eventually have to confess to the bubble's demise. The royal leader informs them that the bubble they destroyed was simply a tourist prop, and with that revelation, shows them the actual oldest bubble, which Patrick inadvertently pops too.
Infuriated, Lord Royal Highness summons the Atlantean Royal Guards to apprehend the group. In a comedic turn of events, Plankton arrives driving the stolen tank and, attempting to fire upon them, discovers that it merely shoots ice cream. Ultimately, Lord Royal Highness captures Plankton and decides his "talking speck" would make an amusing replacement for the bubble that was lost.
As SpongeBob and his friends leave Atlantis for Bikini Bottom aboard the bus, Lord Royal Highness takes the medallion and instructs a guard to discard it. In a final celebration, the characters sing one last song, with only SpongeBob expressing joy at returning home, marking the end of their whimsical adventure.