O povoamento de Novo Cruzeiro iniciou com a chegada do desbravador, Sr. Anastácio Roque. Até o início da segunda metade do século XIX, toda a bacia do Rio Gravatá ainda era inabitada. A região teve seus primeiros habitantes com a fundação da Fazenda Lagoa, hoje distrito de Queixada, Fazenda do Bom Jesus, hoje distrito do Lufa, e Fazenda Gravatá, atual Novo Cruzeiro. Saindo de Araçuaí e seguindo o rio de mesmo nome, o desbravador entrou no afluente Rio Gravatá em busca de pedras preciosas. Ocupou a sub-bacia do Riacho São Francisco e onde hoje está o Bairro Puxa, o Sr. Anastácio Roque e toda equipe acamparam, fundando nesse lugar a primeira residência, mas as pedras preciosas foram tão poucas, que logo decidiram parar com o extrativismo e deram início à agropecuária, tornando grande proprietário de terras então pertencentes ao Município de Araçuaí. Devido à grande quantidade de gravatá que existia, fruto da família do abacaxi, sua propriedade recebeu o nome de “Fazenda Gravatá.”

Naquela época, muitas pessoas desse território morriam com picadas de cobras venenosas, e o índice era tão elevado que deixava a população assustada. No ano de 1917, o bispo da diocese de Araçuaí, Dom Serafim Gomes Jardim da Silva, ordenou que construísse uma capela para o santo protetor da humanidade contra cobras e todos bichos peçonhentos, São Bento. E assim foi feito, a antiga capelinha de São Benedito cedeu o espaço para a outra construção, porém com alvenaria mais moderna. Caracterizou-se um novo aspecto para aquela vila, que muitos já passaram a chamá-la de Vila São Bento.

No início da terceira década do século XX, ocorreu um fato que marcou para sempre a história do lugar, a construção da Ferrovia Bahia/Minas. Os trilhos chegaram em 1924, e a vila de menor expressão tomou um novo rumo tornando-se um centro comercial, atraindo comerciantes vindos de outras regiões, entre eles, várias famílias turcas: Chain, Lauar, Mussi, Barrack, Faid e outras. Na década de 1930, a Vila Gravatá já ultrapassava a vila do Bom Jesus do Lufa em habitantes e no progresso.

Outro marco importantíssimo iniciado na década de 1930 foi a instituição da primeira escola, localizada no centro da Vila, funcionando em um salão com duas turmas e tendo como primeiras educadoras Antonieta Lopes e sua irmã Ina Lopes. A Fundação passou a Escolas Reunidas São Bento em 1944, sendo diretora e também professora a senhora Carmem Silvia Mendes Lages, as professoras Maria do Rosário Nogueira Reis, Maria Adelaide Xavier e Ana Leopoldina Esteves Lima. Em 1946, teve como diretora a Srª Serafina Esteves Lima e passou a Grupo Escolar Inácio Murta, em homenagem ao pai do primeiro prefeito, Sr. Mário Moreira Murta.

Durante os anos quarenta, com o comércio crescendo, a produção atingindo índices mais elevados, os trens da Bahia/Minas escoavam produtos e traziam o oportunidade de acesso à educação, rádio, jornal e informação oral. Dentro desse novo contexto cultural formaram-se grupos de intelectuais que já discutiam a possibilidade de emancipação do distrito. Entre eles estavam Sr. Júlio Campos, Sr. Olímpio Alves, Sr. Mário Murta, Sr Quintino Gomes, Sr. João Alexandrino e outras pessoas de renome.

Em 31 de dezembro de 1943, pelo Decreto Estadual nº 1.058, a Vila Gravatá tornou-se emancipada da cidade de Araçuaí, e, reunidos em assembleia, no dia 01 de janeiro de 1944, cuja pauta era dar novo nome ao Município recém-criado, estava muito difícil para os participantes chegarem a um consenso, pois cada um tinha uma opinião. As pessoas ainda estavam acostumando-se com a nova moeda brasileira, o Cruzeiro, criada em novembro de 1942, em substituição ao Réis. Não tinham o hábito de falar “moeda,” pronunciavam “dinheiro.” Diante da situação, o Sr. Olímpio Alves fez um discurso com palavras que se aproximavam dessas: “Estamos com um novo dinheiro circulando pelo Brasil afora. Ele chegou para melhorar nossas vidas, reduzir a miséria dos mais necessitados. Para que nossa terra tão querida seja próspera e que caminhe rumo ao progresso junto com o Cruzeiro, esse novo dinheiro, que ele nunca há de faltar para nossa gente, nada mais justo que nosso Município receba o nome de “Novo Cruzeiro.” Os demais integrantes da assembleia não tiveram palavras, e por unanimidade, aceitaram o nome sugerido. Foi assim que esse lugar recebeu a denominação de Novo Cruzeiro.

Nos anos sessenta já existia uma diferença de identidade entre as pessoas da cidade e do campo. Em 1962 o prefeito José Moura criou o jornal da cidade (O Novo Cruzeiro) que circulava quinzenalmente. Já podiam contar com Cine-teatro que exibia filmes, apresentação de bandas locais e peças teatrais. A matriz de São Bento sempre foi a igreja mais frequentada. Após as missas, aos domingos, frequentemente havia leilão e barraquinhas. No mês de julho já realizava a festa do padroeiro, São Bento, evento que reunia pessoas das roças e da cidade.

No ano de 1966 aconteceu o que nenhum neocruzeirense gostaria que acontecesse: a Ferrovia Bahia-Minas foi desativada, seus trilhos foram

arrancados. Além da perda do trem, que fazia parte do cotidiano das pessoas, perderam também muitos amigos que eram funcionários da rede e foram transferidos para outras regiões. Até hoje a ferrovia ainda permanece no imaginário de cada um. Nesse contexto, muitas pessoas partiram em busca de melhores condições de vida nos grandes centros. Outras resistiram, seja por falta de recursos, ou por amor à terra, e formaram uma população que construiu com muito trabalho o legado que compõe o nosso patrimônio histórico e cultural.

Assim como outros municípios do Vale do Jequitinhonha, Novo Cruzeiro tem uma forte influência cultural, seja no artesanato, nas festas populares, nos costumes do povo e também na fabricação artesanal de doces, queijos, requeijões, goma (polvilho), biscoitos, farinhas e cachaça de qualidade. O cartão postal da cidade, que todos zelam, é composto pelas antigas construções da Ferrovia Bahia-Minas.

O Município de Novo Cruzeiro hoje é formado pela sede e os distritos de Lufa, Queixada e Novilhona.