Essa histórica cidade, localizada às margens da Lagoa Manguaba, foi a primeira capital de Alagoas.
Segundo Jaboatão (Novo Orbe Seráfico Brasilico, 1761), a área onde se iniciou esse povoado foi registrada, em escritura pública de 5 de agosto de 1591, em nome de Diogo de Mello de Castro. Para conseguir essa escritura, ele fez uma petição a Pedro Homem de Castro, sobrinho e procurador do donatário da Capitania de Pernambuco, Jorge de Albuquerque Coelho. Nessa petição, Diogo de Mello de Castro declara que pedia essa terra para nela fundar uma vila com o nome da Magdalena.
Alguns autores indicam a fundação desse povoado no ano de 1611, pelo donatário da Capitania de Pernambuco Duarte de Albuquerque Coelho.
Em 1633, o povoado foi atacado e incendiado pelos holandeses, a Igreja Matriz foi destruída. Jaboatão, entretanto, relatou que essa foi a única vila da região em que ele não achou registros da ocupação holandesa e que, em 1635, a vila serviu de refúgio para muitos portugueses vindos de Pernambuco, por ordem do general Mathias de Albuquerque. Jaboatão também relatou que o general mandou retirar os franciscanos dos conventos da Paraíba, Igarassu e Ipojuca. Nessa época, o custódio Frei Cosme de São Damião fundou um hospício e um oratório franciscano na Alagoa do Sul. Muitos dos refugiados foram transferidos depois para a Bahia.
Em 1636 a povoação foi elevada à categoria de vila, com o nome de Vila da Madalena, que se tornou a Vila de Santa Maria Madalena da Alagoa do Sul.
O mapa da obra de Caspar Barlaeus, publicado em 1647, registra no local, próximo ao rio Pau Brasil, uma localidade ou capela dedicada a Nossa Senhora da Conceição.
A Vila foi escolhida como sede da Comarca de Alagoas, criada em 1711, subordinada à Capitania de Pernambuco.
Segundo Jaboatão, na segunda metade do século 18, a Igreja Matriz era dedicada à N.S. do Rosário. Existia o Hospício dos RR. PP. do Carmo Observante, a capela de N.S. do Ó e o Convento de São Francisco.
Em 1817, a Vila de Alagoas tornou-se a capital da recém criada Capitania de Alagoas. Em oito de março de 1823, a Vila foi elevada à condição de Cidade de Alagoas, que se tornou capital da Província de Alagoas.
Em 5 de agosto de 1827, nasceu nessa Cidade de Alagoas, Manuel Deodoro da Fonseca, que veio a se tornar o primeiro presidente da República.
Em 1939, a capital foi transferida para Maceió.
Hoje, Marechal Deodoro é um dos principais destinos turísticos do Estado, com suas praias, patrimônios históricos e eventos culturais.
