A história começa com o narrador falando sobre a Ordem da Pedra: Gabriel Guerreiro, Ellegaard o Engenheiro Redstone, Magnus Rogue, e Soren o Arquiteto. A Ordem conseguem derrotar o Dragão do End e escapuliu em lenda. No presente, Jesse, Olivia, Axel, e porco de estimação de Jesse, Reuben, estão se preparando para a competição Edifício Endercon, e eles decidem sobre a qual mob para fazer. Depois de reunir os suprimentos, eles cabeça para a concorrência e decidir sobre um nome da equipe. Uma equipe rival, Os Ocelots, votos para vencer a competição novamente, chamando a equipe de Jesse "A Ordem dos vencidos". No entanto, a equipe de Jesse concluída a sua construção, chamando a atenção dos juízes e de outros construtores. Aiden, um membro dos Ocelots, derrama intencionalmente lava em traje de Reuben, definindo-o no fogo com Reuben correndo para dentro da floresta. Jesse, então, decide que quer deixar suas / seus amigos ficar e proteger a compilação, ou continuar com Jesse e encontrar Reuben.
Na mata, Jesse é capaz de encontrar Reuben escondido atrás de alguma grama alta, mas eles são atacados por um grupo de mobs hostis. Depois de encontrar um beco sem saída, o jogador decide se que Reuben deve correr de volta para Endercon, ou ficar com Jesse para a proteção. Depois de ouvir gritos de Jesse por ajuda, Petra vem em auxílio de Jesse, e retirar-se para uma caverna nas proximidades. Na caverna, Petra mostra Jesse um crânio murchar que ela recebeu do Nether, e diz Jesse que um homem na Endercon está negociando seu crânio para um diamante. Jesse se sente suspeito no início, mas relutantemente aceita a ajudá-la. No caminho para fora da caverna, eles estão paradas em uma ponte com mobs hostis carga em ambas as direções. Sem saída, que quer salto ou luta, e voltar para Endercon.
De volta ao Endercon, Jesse felicita suas / seus amigos em ganhar a competição (ou anima-los, se perder), e é um gesto de Petra para passar para o "beco escuro" para o comércio. No beco, eles encontram Ivor, que trocam o crânio murchar com o. Petra é enganado com lápis-lazúli, e ela e Jesse tentativa de parar Ivor. No portão para o salão, o porteiro não vai permitir que eles em menos que tenham bilhetes, mas depois descobrir que o porteiro tem medo de galinhas. Chegando-se com um plano, eles usam um bloco de lodo para abrir a fazenda de galinha, fazendo com que o porteiro para tornar-se distraído e permitindo Jesse e seus / suas amigas para ir no salão.
No salão, o grupo encontrar uma porta aberta e esgueirar-se para dentro para encontrar a sala secreta de Ivor. Jesse puxa uma alavanca para revelar um baú com dois crânios murcha, e um padrão na parede. Lukas lhes diz que Ivor tem a intenção de criar um Wither para destruir a convenção, e todos concordam que pará-lo. Tendo apanhado Ivor em seu esquema, Ivor recua com sucesso grupo de Jesse de volta ao palco principal gerando um golem de ferro. Como Gabriel está falando para a multidão, Ivor aparece e puxa uma alavanca, revelando a Wither. A Wither consome o bloco de comando conectada ao corpo, criando a tempestade Wither. O grupo de Jesse, Gabriel, e Ivor todos recuo para o templo de Gabriel, onde um portal inferior é encontrado. Jesse ilumina o portal para cima e algumas de suas / seus amigos passar, mas Jesse fica para trás para ajudar Petra e Gabriel lutando contra a tempestade Wither. Assim como Jesse tenta salvá-los, ele é batido para trás por um tentáculo da tempestade Wither no portal inferior com Lukas.
No Nether, o grupo de Jesse de amigos (menos Petra) confrontar Ivor, onde Ivor diz Jesse que a pista minecart é a única maneira de sair do Nether. Esquivando-se algumas bolas de fogo Ghast, amigos de Jesse chegar com segurança ao outro portal inferior, que os leva a uma colina penhasco-slide no mundo superior. Eles, então, decidir se a fazer uma cabana ou uma casa na árvore e descansar para recarregar para a viagem ao templo. Na parte da manhã, os amigos de Jesse encontrar o templo, onde é revelado que Ivor foi um dos membros da Ordem da Pedra, mas foi expulso quando ele desconfiava Gabriel. Eles, então, usar o amuleto para descobrir onde está o resto da Ordem são, e o jogador escolhe se quer encontrar Magnus com Axel, ou encontrar Ellegaard com Olivia.