Após o término do contrato da Pepsi com Michael Jackson em 1993, garantir um novo patrocinador tornou-se uma prioridade financeira crucial para a próxima turnê do Rei do Pop.
Charles Bobbit, renomado empresário que já havia trabalhado com James Brown e assessorado Michael durante a segunda metade de sua turnê em Bremen, desempenhou um papel fundamental ao conectar o cantor com o príncipe Al-Walid. Este último, reconhecido como um empresário de reputação impecável na década de 1990, havia desempenhado um papel vital na recuperação da Euro Disney após a abertura de seu parque temático em Marne-le-Vallée, na França.
Em agosto de 1995, enquanto Michael estava na França e hospedado no Disneyland Hotel, nas proximidades do parque temático, seu advogado, John Branca, o acompanhava. Durante sua estadia no país, MJ encontrou-se com o bilionário saudita, onde discutiram possíveis colaborações que poderiam aproveitar seus talentos individuais.
Al-Walid reconheceu o potencial de trabalhar com Michael, percebendo que o cantor, com poucos parceiros e patrocinadores dispostos a investir nele, buscava reiniciar suas atividades e explorar novos empreendimentos. Esse interesse mútuo levou a uma reunião mais detalhada, realizada no Beverly Wiltshire Hotel em Beverly Hills.
Na ocasião, o Rei do Pop compareceu acompanhado por Charles Bobbit, John Branca e seu amigo de infância John McClain, uma figura influente na indústria musical que, na época, gerenciava a carreira de Janet Jackson.
Naquele momento, Branca e McClain tinham uma relação superficial, sem saber que eventualmente se tornariam os administradores do Espólio de Michael. Al-Walid, por sua vez, estava acompanhado por seu sócio e amigo, o empresário e produtor tunisiano Tarak Ben Ammar.
O assunto desta reunião foi o financiamento da turnê do álbum HIStory. Não satisfeito em patrocinar os shows, o príncipe apresentou a Michael suas ideias de projetos no campo do entretenimento familiar: parques temáticos, canais de televisão, filmes, hotéis e cassinos.
O empresário saudita estava ciente de que a imagem de Michael ainda era muito lucrativa na Europa e na Ásia, então ele não hesitou em se associar a ele.
Os termos de seu contrato nunca foram divulgados. A aliança de Michael e Príncipe Al-Walid se solidificou com a Kingdom Entertainment, cuja formação foi anunciada em uma coletiva de imprensa em Paris em 19 de março de 1996. Sua principal atividade era apoiar a turnê HIStory.
Durante os anos de 1996 a 1997, Michael se distanciou de seus assessores nos Estados Unidos, rompeu com seu empresário Sandy Gallin e, com essa nova equipe, mergulhou de cabeça na turnê HIStory.
A turnê começou em Praga, República Checa, com uma agenda apertada, permitindo a Michael percorrer os quatro cantos da Europa. Como uma máquina, a turnê HIStory percorreu as maiores arenas do Velho Mundo, onde o Rei do Pop apresentou seus maiores sucessos.
Visualmente, a turnê HIStory foi excelente. Todos os recursos tradicionalmente usados em shows de rock foram colocados de lado em favor de produções cênicas em grande escala que poderiam recriar os ambientes encontrados nos videoclipes de Michael.
Embora tenha tido menos shows do que a turnê Bad, a turnê HIStory foi capaz de atrair muitas pessoas e render ainda mais lucros: ao longo de 82 apresentações, a turnê vendeu mais de quatro milhões de ingressos e arrecadou mais de US $165 milhões.
