The story begins with the narrator talking about the Order of the Stone: Gabriel the Warrior, Ellegaard the Redstone Engineer, Magnus the Rogue, and Soren the Architect. The Order manage to defeat the Ender Dragon and slipped away into legend. In the present, Jesse, Olivia, Axel, and Jesse's pet pig, Reuben, are preparing for the Endercon Building Competition, and they decide on which mob to make. After gathering the supplies, they head to the competition and decide on a team name. A rival team, The Ocelots, vows to win the competition again, calling Jesse's team "The Order of the Losers". Nonetheless, Jesse's team completes their build, drawing attention from judges and other builders. Aiden, a member of the Ocelots, intentionally spills lava on Reuben's costume, setting it on fire with Reuben running off into the woods. Jesse then decides to either let his / her friends stay and protect the build, or go on with Jesse and find Reuben.
In the woods, Jesse is able to find Reuben hiding behind some tall grass, but they are attacked by a group of hostile mobs. After finding a dead end, the player decides whether that Reuben should run back to Endercon, or stay with Jesse for protection. After hearing Jesse's cries for help, Petra comes to Jesse's aid, and they retreat to a nearby cave. In the cave, Petra shows Jesse a wither skull that she got from the Nether, and tells Jesse that a man at Endercon is trading her the skull for a diamond. Jesse feels suspicious at first, but reluctantly accepts to assist her. On the way out of the cave, they are stalled on a bridge with hostile mobs charging at both directions. With no way out, they either jump or fight, and return back to Endercon.
Back at Endercon, Jesse congratulates his / her friends on winning the competition (or cheers them up if they lose), and is motioned by Petra to move to the "dark alley" for the trade. In the alley, they meet Ivor, who they trade the wither skull with. Petra is scammed with lapis lazuli, and she and Jesse attempt to stop Ivor. At the gate to the hall, the usher will not allow them in unless they have tickets, but they later find out that the usher is afraid of chickens. Coming up with a plan, they use a slime block to break open the chicken farm by jumping up to it, causing the usher to become distracted and allowing Jesse and his / her friends to go in the hall.
In the hall, the group find an open door and sneak inside to find Ivor's secret room. Jesse pulls a lever to reveal a chest with two wither skulls, and a pattern on the wall. Lukas tells them that Ivor has intended on creating a Wither to destroy the convention, and they all agree to stop him. Having caught Ivor in his scheme, Ivor successfully retreats Jesse's group back to the main stage by spawning an iron golem. As Gabriel is talking to the crowd, Ivor shows up and pulls a lever, revealing the Wither. The Wither consumes the command block attached to its body, creating the Wither Storm. Jesse's group, Gabriel, and Ivor all retreat to Gabriel's temple, where a nether portal is found. Jesse lights the portal up and some of his / her friends go through, but Jesse stays behind to aid Petra and Gabriel fighting off the Wither Storm. Just as Jesse attempts to save them, he / she is knocked back by a tentacle of the Wither Storm into the nether portal with Lukas.
In the Nether, the Wither Storm destroys the portal, and Jesse's group of friends (minus Petra) confront Ivor, where Ivor tells Jesse that the minecart track is the only way out of the Nether. Dodging some ghast fireballs, Jesse's friends safely arrive at another nether portal, which leads them to a cliff-slide hill in the Overworld. They then decide on whether to make a hut or a treehouse and rest to recharge for the trip to the temple. In the morning, Jesse's friends find the temple, where it is revealed that Ivor was one of the members of the Order of the Stone, but was kicked out as he distrusted Gabriel. They then use the amulet to find out where the rest of the Order are, and the player chooses whether to find Magnus with Axel, or find Ellegaard with Olivia.