Inaugurado em 23 de maio de 1942, o Cine Teatro Cuiabá faz parte da cultura e história cuiabanas. Idealizado na década de 30 para atender à população cuiabana, que clamava por um lugar onde fossem realizadas manifestações artísticas e a exibição de filmes. A solução encontrada pelo então interventor do Estado, Julio Muller, foi a construção do Cine Teatro Cuiabá.

A história do cinema, no entanto, começou muito antes, em 1912. Foi naquela época que Cuiabá aprendeu a apreciar filmes, com o Cinema Parisien. O primeiro cinema do Estado funcionava no mesmo prédio do antigo teatro "Amor à Arte", situado na rua Formosa, hoje Joaquim Murtinho esquina com a Getúlio Vargas, único da cidade à época.

  
Com a desativação do cinema, em 1939, Cuiabá ficou sem um espaço para a realização de shows, peças de teatro e exibição de filmes. Nasceu assim o Cine Teatro Cuiabá. Sua inauguração foi um grande evento. Em maio de 1942, era grande a excitação da população cuiabana com a inauguração do cinema, super moderno e luxuoso para os padrões da época.

     
O nome do primeiro filme que seria exibido pelo Cine Teatro foi mistério durante meses em Cuiabá. Os jornais faziam investigações e especulações sobre o assunto. Até apostas foram feitas. Após a elucidação do mistério, o jornal "O Estado de Mato Grosso" publicou na capa: "Desvendada a incógnita", revelando o nome do primeiro filme do cinema: “A noiva veio como encomenda”, estrelado por Betty Davis e James Cagney.
      
No dia 23 de maio de 1942 o Cine Teatro Cuiabá foi inaugurado com uma sessão inaugural magnífica, contando com a presença do Chefe Maior do Estado: Julio Strubling Muller.

Na década de 50, era comum o Cine Teatro receber artistas de renome nacional, como a cantora Angela Maria, e internacional, como o grupo Los Panchos. Mais novidades são implantadas no ano de 1958, quando o Cine Teatro passa a contar com a tecnologia do cinemascope - a antiga imagem achatada torna-se retangular e permite melhor visibilidade das cenas. Apesar de a maioria dos filmes serem exibidos em Cuiabá, três, quatro anos depois do seu lançamento, as produções ficam na memória da comunidade. 

Em 1984 o Cine Teatro é tombado como Patrimônio Histórico por meio da Portaria n°30/31/84, mas é desativado em 1997 por várias circunstâncias administrativas e sanitárias. O fechamento do “cine teatro” cria então, uma lacuna na vida cultural cuiabana.