Interior da Catedral Metropolitana de Cuiabá - Foto: Mateus Hidalgo (Licença-cc-by-sa-2.5)

Fundação
Os primeiros indícios dos bandeirantes paulistas na região onde hoje fica a cidade datam de 1673 e 1682, quando da passagem de Manoel de Campos Bicudo. Ele fundou o primeiro povoado da região, onde o rio Coxipó deságua no Cuiabá, batizado de São Gonçalo. Em 1718, chegou ao local, já abandonado, a bandeira do sorocabano Pascoal Moreira Cabral. Em busca de indígenas, Moreira Cabral subiu o Coxipó, onde travou uma batalha com os índios coxiponés. Como perderam a batalha, os bandeirantes voltaram e no caminho encontraram ouro, deixando, assim, a captura de índios para se dedicar ao garimpo.

Em 1719, Pascoal Moreira foi eleito, em uma eleição direta em plena selva, comandante da região de Cuiabá. Em 8 de abril de 1719, Pascoal assinou a data da fundação de Cuiabá no local conhecido como Forquilha, às margens do Coxipó, de forma a garantir os direitos pela descoberta à Capitania de São Paulo. A notícia da descoberta se espalhou e a imigração para a região tornou-se intensa.

Consolidação
Já em 1726, chega, à Cuiabá, o capitão-general governador da Capitania de São Paulo, Rodrigo César de Menezes, como representante do Reino de Portugal. Em 1 de janeiro de 1727, Cuiabá foi elevada à categoria de vila, com o nome de Vila Real do Senhor Bom Jesus de Cuiabá. Tem-se confundido muito a fundação do arraial da Forquilha por questões ideológicas.

Estudos historiográficos há muito já traçaram a diferença entre uma e outra fundação, alegando-se que o 1° de janeiro seria a data de elevação do arraial da Forquilha à categoria de vila, o que é um contrassenso, pois não se pode fundar um município num lugar que só viria a ser descoberto anos depois. Porém, a data de 8 de abril se firmou como data do município, desejosa de ser a primeira do oeste brasileiro. Logo, contudo, as lavras se mostraram menores que o esperado, o que acarretou um abandono de parte da população.

Expansão
Somente após a Guerra do Paraguai e o retorno da navegação pelas bacias dos rios Paraguai, Cuiabá e Paraná é que o município voltou a crescer. A economia nesse período tinha suas bases na produção da cana-de-açúcar e no extrativismo. Esse momento produtivo não duraria muito e o município voltou a ficar estagnado, desta vez até 1930. A partir daí, o isolamento foi encerrado com as ligações rodoviárias com Goiás e São Paulo e a aviação comercial. A explosão no crescimento deu-se depois da década de 1950, com a transferência da Capital Federal e o programa de povoamento do interior do país.

Nas décadas de 1970 e 1980, o município cresceu muito, mas os serviços e a infraestrutura não acompanharam este ritmo. O agronegócio expandiu-se pelo estado e o município começou a modernizar-se e industrializar-se. Após o ano de 1990, a taxa de crescimento populacional diminuiu e o turismo começou a ser visto como fonte de bons rendimentos.