Os primitivos habitantes desse território foram os índios caiapós, que tinham aldeia localizada nas terras onde hoje se encontra a cidade de Carinhanha, vivendo em completa harmonia, quando, pelo ano de 1712, presumivelmente, nele penetrou pela primeira vez o homem civilizado. Segundo a tradição local, coube essa primazia ao famoso bandeirante Manuel Nunes Viana, vencedor dos paulistas, na Guerra dos Emboabas. Em busca do rio das Velhas, atingiu a margem esquerda do rio São Francisco e indo para o sul atravessou o mesmo na confluência com o rio Carinhanha ou Carunhenha, onde encontrou um aldeamento de índios caiapó, resultando numa luta sangrenta e fracasso dos índios. Aí o bandeirante fixou base para suas conquistas, local que posteriormente veio a ser o centro de intercâmbio entre a Bahia e o estado de Minas Gerais.

Muitos queriam que o nome do local fosse Carunhanha, isto é, loca de sapo, entretanto, a maioria atribui o topônimo indígena à grande quantidade de aves de nome Carunhenha existente no lugar, hoje raramente encontradas nas margens das lagoas. Outros já dizem que o nome é derivado de uma índia de nome Nhanha com a junção de um peixe, carí, dando assim o nome então de cainhanha. Em 1832, o julgado de São José de Carinhanha, pertencente à comarca do Rio São Francisco foi elevado à categoria de vila, sendo criado também o município, com território desanexado do território de Barra do Rio Grande. Sua sede recebeu foros de cidade em 1909.