Em 1965, houve neste período de tempo a primeira tentativa de emancipação de Setubinha, que fracassou derrotado em urnas. Em 1994, então o vereador Teófilo Barbosa Neto, organizador do movimento pró-emancipação, encontrou pessoas influentes na politica de minas e com seu grande empenho, sagrou-se vitorioso em plebiscito realizado no dia 10 de outubro de 1995, com mais de 90% dos votos válidos e em 21 de dezembro de 1995, através da Lei Estadual nº 12030, Setubinha foi elevado á categoria de município, sancionada pelo governador Hélio Garcia.

Ainda que grande parte dos documentos referentes ao município, tenha se perdido em duas enchentes do Rio Araçuaí, muito se conservou de sua história, que é mais antiga do que a história de Malacacheta. Por volta de 1830, à região foi visitada por um português, cobrador de impostos e Guarda-mor do Império, chamado Jerônimo. Este, a caminho de Teófilo Otoni, seguindo a trilha aberta por Benedito Otoni (com o objetivo de descobrir afluentes do Rio Mucuri que o levassem ao mar – na Bahia) passando por Setubinha na época Sesmaria de uma família originária da cidade portuguesa de Setúbal – resolveu instalar-se definitivamente no local.

O principal rio desta sesmaria recebeu o nome de Setúbal em homenagem à cidade natal dos portugueses. Parte dela, que foi doada para outra família, tinha sua área territorial banhada por um afluente do rio Setúbal, que por ser de menor porte, recebeu o nome de Setubinha, originando-se, assim, o nome atual do município:

Setubinha. As terras visitadas foram doadas em sesmaria a uma outra família portuguesa, de nome Batista de Miranda, que nelas construiu as primeiras casas, por volta de 1840. Em 1841, a povoação conhecida como Santo Antônio do Setubinha, já servia de referência para Cassimiro Gomes Leal. Por ela passaram, em 1847 e 1852, as expedições de Teófilo Benedito Otoni rumo ao Vale do Mucuri. Novas famílias, algumas de tradição mineira como a Paula Dias, que descende de Alvarenga Peixoto, foram chegando e trazendo o progresso para a povoação, que se tornou Paróquia e foi elevada à categoria de Distrito de Minas Novas.