Minions are small, yellow pill-shaped creatures which have existed since the beginning of time, evolving from single-celled organisms into beings which exist only to serve history's most evil masters, but they accidentally end up killing all their masters: rolling a T. rex into a volcano, letting a caveman get eaten by a bear, crushing a Pharaoh to death with a pyramid, and exposing Count Dracula to sunlight. They are driven into isolation after firing a cannon at Napoleon while in Russia, and start a new life inside a cave, but after many years, the Minions become sad and unmotivated without a master to serve. However, three Minions named Kevin, Stuart and Bob decide to go out on a quest to find a new master.

The three journey in 1968 to New York City, where they enter a department store for the night and stumble upon a hidden commercial broadcast advertising Villain-Con, a convention for all villains in Orlando. The next day, they manage to hitchhike a ride with the Nelsons, a family of thieves. At the convention, they meet Scarlet Overkill, the world's first female supervillain, who unexpectedly hires them and takes them to her home in London. They phone the rest of the Minions to get them to join. Scarlet plans to steal the Imperial State Crown from Queen Elizabeth II, promising to reward the Minions if they succeed, but also threatening to kill them if they fail.

Scarlet's husband Herb supplies them with inventions to aid in the heist, but they are nearly caught while breaking into the Tower of London. During the subsequent chase, Bob slams into the Sword in the Stone and pulls the sword free to defend himself and his friends, removing the Queen from the throne and making Bob the new King. Enraged that someone else accomplished her dream of stealing the throne, Scarlet confronts Bob, who voluntarily abdicates the throne in her favor. Undeterred, Scarlet imprisons Kevin, Stuart and Bob in a dungeon, where Herb attempts to torture the trio, but they escape with the intention to apologize to Scarlet at her coronation.

After making their way to Westminster Abbey, Kevin, Stuart and Bob interrupt the coronation by inadvertently dropping a chandelier on Scarlet. Mistaking the accident for an assassination attempt, Scarlet angrily orders the trio's execution and has other villains chase them through the streets of London during a thunderstorm. Stuart and Bob are captured, while Kevin hides in a pub and sees Scarlet on television, who declares that she will kill Stuart and Bob if Kevin does not show up by dawn. With the villains still searching for him, Kevin sneaks into Scarlet's castle to steal weapons and triggers a machine Herb was building, causing him to grow in size into a giant. Kevin tramples through London, rescues his friends, and battles Scarlet, just as the other Minions turn up in the city. Scarlet tries to eradicate them by firing a massive missile, but Kevin swallows it. Scarlet and Herb attempt to escape with her rocket dress, only for Kevin to hold onto it and get pulled into the sky. The missile explodes, seemingly killing Kevin, Scarlet, and Herb. As the Minions mourn the loss of their leader, Kevin survives as he returns to his normal size.

The Queen gets her throne and crown back. She rewards Bob with a tiny crown for his teddy bear Tim, Stuart with an electric guitar, and Kevin with a knighthood. Scarlet and Herb, still alive, steal the crown again, only to be stopped by a young Gru, who fires a freeze ray at them and