No final do século XVIII, exploradores portugueses à procura de ouro se fixaram na região e fundaram o povoado de Remédios, hoje localizado em território de Novo Horizonte, cujo nome se deve à crença de que as águas jorrantes da serra tinham propriedades medicinais. Remédios é também o local em que se originou Ibitiara e foi sede desse município até 1925.[4]
Em 1937, o garimpeiro José Firmiano de Souza, mais conhecido como Zé Salão, construiu um barracão, onde comprava ouro. Ali permanecendo com sua família, construiu sua casa, ao lado do barracão, e comprou as terras, pertencentes a um homem chamado Marcelino. Outras pessoas foram construindo casas próximas à de Zé Salão, formando um povoado, chamado Marcelino.[5]
Em 1949, foi organizada a primeira feira livre por Zé Salão e seu genro Deocleciano Manoel dos Santos (Béu). As mercadorias não vendidas de feiras das proximidades, como Ibiajara, Seabra e Ibitiara, eram vendidas na feira do povoado de Marcelino, que rapidamente se desenvolveu, adquirindo o nome Novo Horizonte, o qual foi dado por acreditar que daria um novo horizonte às próximas gerações.[5][6]
A Lei Estadual nº 5020, de 13 de junho de 1989, elevou o povoado de Novo Horizonte à categoria de município, desmembrado de Ibitiara.[5][6]
Segundo o censo de 2022, Novo Horizonte possui uma população de 11.162 habitantes.[8] No entanto, há uma grande população flutuante, devido à mineração de quartzo rutilado.[9]