Agents Pablo and Tyrone, the best delivery agents who never lose a package, have to bring an Asian elephant to the Dandeli Wildlife Sanctuary for Park Ranger Tasha, but Miss Rhamaswami and Austin-Ji try to steal the elephant and bring it to their house and keep it as a pet.
Pablo and Tyrone are in the backyard wearing dark shades, or glasses. They introduce themselves to the viewer as delivery agents. They sing the song We Are Delivery Agents as they explain their job. The backyard transforms into an Indian landscape as the two run into the grass.
They meet Park Ranger Tasha and she tells them that their next delivery mission is to deliver an Asian elephant to Dandeli Wildlife Sanctuary. They take the delivery car to the train as they discuss how they won't let bad guys take the package. Meanwhile, Uniqua, who is pretending to be Miss Rhamaswami, and her assistant Austin-Ji are planning to steal the elephant. They succeed in retrieving the elephant as they steal the delivery agents' car. Pablo and Tyrone take a jeep to catch up with the elephant.
Miss Rhamaswami and Austin-Ji get on a train, the same train as Tasha did. Tasha hears an elephant noise and wonders if it was her imagination. The friends sing Havin' An Elephant As A Pet as Miss Rhamaswami daydreams about her elephant. The delivery agents use a grappling hook to swing from their jeep to the train. They tell Miss Rhamaswami to hand over the elephant, but Austin-Ji innocently tells them that the elephant belongs to her now. Pablo says the elephant the needs to be somplace where it's safe, but Miss Rhamaswami naively declares that he's happy with her. During their conversation, the elephant escapes them all and runs off. The four briefly pursue the elephant together. Austin-Ji marvels at how the elephant got away so easily, and Tyrone explains that it's because they have padded feet, making their footsteps quiet. After this, Miss Rhamaswami and Austin-Ji run off on their own as they continue their pursuit, but the elephant gets lost in a market. The delivery agents catch up with Austin-Ji and Miss Rhamaswami and try to find the elephant while singing Elephant, Where Could You Be?. The elephant-stealing team finds the elephant and enter Miss Rhamaswami's private jet.
The delivery agents run to the plane, trying to get on. They get on to the plane and fly in the cargo hold. They walk up to the room where Miss Rhamaswami and Austin-Ji are sitting on chairs. Rhamaswami shows the elephant her most prized possessions, including her well-loved collection of fancy cookie jars. The elephant knocks over the most expensive one, but luckily Miss Rhamaswami catches it. Austin-Ji tries to tell her that having an elephant as a pet is a bad idea, but Miss Rhamaswami will not listen.
The agents try to lure the elephant out of the room. They succeed in doing so, and give the elephant multiple parachutes so they can get to the wildlife sanctuary. Meanwhile, at the sanctuary, Tasha is waiting patiently. She says that she does not see the agents anywhere. The delivery agents fly down with parachutes along with the elephant and present it to Park Ranger Tasha. Tasha is grateful, but her thanking is interrupted by Austin-Ji and Miss Rhamaswami, who are angry and want to get back their "pet".
Miss Rhamaswami says that the elephant will live in her house, but Agents Pablo and Tyrone, who are surprised by this notion, tell her that a house is no place for an elephant.
Tasha helps the two see reason by explaining that it would be wrong to have an elephant for a pet because elephants need open land and friends to play with. She tells Miss Rhamaswami that the Dandeli WIldlife Sanctuary provides all of this for the elephant, but she also reassures her that she can come visit the elephant anytime she likes. Feeling encouraged, Miss Rhamaswami decides to keep the elephant at the sanctuary. They all sing Right Where She Belongs as they happily observe the elephants in their natural habitat. At the end of the song, Miss Rhamaswami says goodbye to the elephant as she leaves with her own kind.
Tyrone invites everyone over for mango lassi at his house as the nature reserve transforms back into the backyard. They sing the end song and enter Tyrone's house. Pablo and Tyrone open the previously closed door and shout "We never lose a package!".