O desbravamento da região, hoje ocupada pelo município de Santa Maria Madalena, data de 1840, quando por ali passou o português Manoel Teixeira Portugal. Logo depois, se estabeleceu no local o mateiro José Vicente, que ali chegou em perseguição a negros fugitivos e armou um rancho no mesmo local do antecessor.

Segundo a lenda, as referidas terras foram cedidas em troca de uma espingarda de fabricação suíça ao padre Francisco Xavier Frouthé, que doou parte delas para edificação de uma capela em homenagem a Santa Maria Madalena, em cumprimento de promessa.

Se do fato, com aparência de lenda, não há senão notícia oral, existe, todavia, a escritura lavrada em notas do escrivão de paz Antônio Leoclat, da freguesia de São Francisco de Paula, terceiro Distrito da Vila de Cantagalo, em 20 de abril de 1850, que vem abonar em parte a afirmativa tradicional.

Devido aos pântanos cheios de barro branco, os viajantes que demandavam a estrada Cantagalo-Macaé, davam ao local o nome de Tabatinga, que foi a primeira denominação do Arraial do Santíssimo, atual cidade de Santa Maria Madalena.

A elevação à categoria de freguesia se deu em 1855 e à de vila em 1861, desmembrada do termo de Cantagalo e tendo anexadas a si as freguesias de São Francisco de Paula e São Sebastião do Alto. Destacou-se na luta pela elevação a município o coronel Braz Fernandes Carneiro Viana, cunhado do Duque de Caxias. Santa Maria Madalena passou à categoria de cidade em 1862.