A cidade nasceu de um entreposto comercial entre Minas Gerais e o Rio de Janeiro que se transformou na Vila de Rodeio, ponto convergente entre estes estados e São Paulo. A povoação floresceu no fim do século XIX com a construção da Estrada de Ferro Dom Pedro II, que passou a cortar a vila.
Mais tarde, em 1943, passou a chamar-se Soledade de Rodeio, e em seguida (1946) Engenheiro Paulo de Frontin, em homenagem ao responsável pela duplicação da linha férrea, especialmente pelo Tunel 12 ou "Túnel Grande", que possui 2.245 metros de comprimento.
Entre outras obras do engenheiro, destaca-se a de abastecimento de água que, realizada em apenas 6 dias, salvou a cidade do Rio de Janeiro de uma grande seca, obra esta que contou com a participação do também engenheiro Raimundo Teixeira Belfort Roxo[7].
Engenheiro Paulo de Frontin se situa às margens de uma ferrovia, a Linha do Centro da antiga Estrada de Ferro Central do Brasil, onde no trecho de subida pela Serra do Mar, é possível apreciar uma bela vista da região do Vale do Café. Até 1996, o município era atendido pela antiga Linha Barrinha, uma linha de subúrbio operada pela Rede Ferroviária Federal (RFFSA), que o ligava ao município de Japeri, no deslocamento até a capital fluminense e à cidade de Barra do Piraí. Atualmente, somente há o tráfego de trens cargueiros na cidade. [8]
