Sabe-se que o povo indígena xavánte habitava a região. Os paulistas nomeiam nesta porção territorial um antigo povo denominado araés. Desse povo não se tem maiores informações. O povo indígena xavante sujeitou-se a migrações, buscando regiões mais ao sul e se encontra confinado em áreas indígenas circunscritas. Apesar do termo Nova Xavantina, originar-se do povo xavánte, não se encontra mais no município remanescentes dessa gente em vida tribal organizada. Pela região de Nova Xavantina, em função do Rio das Mortes, diversas expedições cortaram seu território, desde o século XVII. Que hoje é território do município de Nova Xavantina, teve movimentação por conta de seringueiros, no fim do século passado e no começo deste. Sem, no entanto, que se tenha registrado notícias concretas dessa época.
A denominação de Xavantina provinha do nome dado ao povo primitivo da região - o xavánte. No entanto, a denominação xavánte foi dada pelos segmentos da vida nacional. A autodenominação deste povo é a'úwe. Entretanto, apesar do prestigio político ocorrido na sua fase embrionária, a vida organizada de Xavantina foi acontecendo bem mais tarde. Com a abertura da BR-158, nasceu o povoado de Nova Brasília, na margem esquerda do Rio das Mortes, frente ao primeiro povoado de Xavantina, este, situado à margem direita. O primeiro povoado, Xavantina, cresceu mais rapidamente e ali se fundou o Distrito Ministro João Alberto, pela Lei n.º 2.059, de 14 de dezembro de 1963. Assim a primeira denominação de Xavantina, foi Ministro João Alberto. Alguns anos depois, também o povoado da margem esquerda do Rio das Mortes, Nova Brasília, passou a distrito, fato que deu-se através da Lei n.º 3.759, de 29 de junho de 1976, não sendo alterado o nome da povoação.
Chegou a maturação do município. A Lei n.º 4.176, de 3 de março de 1980, de autoria do deputado Ricardo Corrêa, criou o município:
"Artigo 1º - Fica elevada a categoria de município, com a denominação de Nova Xavantina, a localidade do mesmo nome, integrante do município de Barra do Garças;
• Ficam extintos os distritos de Ministro João Alberto e Nova Brasília, criados, respectivamente pelas leis n.º 2.059, de 14/02/1963 e n.º 3.759, de 29/06/1976.
• Cria-se o distrito de Nova Xavantina, cujos limites coincidem com os do município...
Artigo 2º - Nos termos da Lei Complementar Federal n.º 01, de 09 de novembro de 1967, o município de Nova Xavantina será instalado a 31 de janeiro de 1981, com a posse do prefeito, vice-prefeito e vereadores, a serem eleitos em 15 de novembros de 1980."
Com a formação do município, extinguiram-se os dois distritos pré-existentes. E não apenas juridicamente e administrativamente se explica a alteração de nome dos distritos para o município, mas uma razão histórica determinou a mudança de nome. Na verdade, se tratava de uma só povoação, separada pelo Rio das Mortes: a povoação de Xavantina da margem direita do rio e a povoação de Nova Brasília, na margem esquerda. Conveniência administrativas e políticas alteraram a denominação da povoação de Nova Brasília. Com a criação do município, administrativamente desapareceriam os dois distritos, por não haver razão para manutenção de dois. Surgia, então a luta popular pela prevalência do nome próprio, que passaria a ser do município. Em se tratando de uma povoação apenas, surgiu a proposta de se unir os dois nomes populares num só. Xavantina contribuiu com sua própria denominação, enquanto que Nova Brasília, nome composto, contribuiu com o têrmo "Nova". A denominação "Nova" de Nova Xavantina, não nasceu por diferenciação de algum município denominado Xavantina, mas por razão interna de uma povoação, que fundiu duas outras anteriores.