Born the third child of a large military family in Alagoas, in a town that today bears his name (and of which his older brother Severino Martins da Fonseca was the 1st Baron), son of Manuel Mendes da Fonseca Galvão and wife Rosa Maria Paulina de Barros Cavalcanti, Fonseca made a military career, putting down the Praieira revolt in Pernambuco, in 1848, which was Brazil's response to the European year of failed liberal revolutions. He also saw action during the War of the Triple Alliance (1864–1870), attaining the rank of captain, and was later (1884) raised to field-marshal, and then to full marshal. His personal courage, military competence and manly style made him a national figure.

As Governor of Rio Grande do Sul, Fonseca was courted by republican intellectuals such as Benjamin Constant and Rui Barbosa in the café society of São Paulo. In 1886, alerted that the imperial government was ordering the arrest of prominent republicans, Fonseca went to Rio de Janeiro and assumed leadership of the army faction that was favorable to the abolition of slavery. Emperor Pedro II had advocated the abolition of slavery for decades, freeing his own slaves in 1840, but he believed slavery should be done away with slowly so as not to damage the economy. His daughter, Isabel, Princess Imperial of Brazil, abolished slavery in 1888, during her third regency (while her father was away from the country). Enraged oligarchs played a role in the subsequent coup d'état. Fonseca's prestige placed him at the head of the military coup that deposed the emperor, November 15, 1889, and he was briefly the head of the provisional government that called a Constituent Congress to draft a new constitution for a United States of Brazil. Soon, however, he was in conflict with the civilian republican leaders.

His election as president in February 26, 1891, by a narrow plurality, was backed by military pressure on Congress. A few days later he took the oath of office at the Paço de São Cristóvão, the former imperial palace in Rio de Janeiro.

The Fonseca administration, divided by political and personal animosity between the president and vice president Floriano Peixoto, encountered strong opposition within the Congress, which chose a policy of obstruction. During the first months of his presidency, he permitted his ministers almost unrestricted control of their ministries. Arbitrary presidential decrees, including concession of the port of Torres to a private company, a stroke of corporate nationalism in the style of Napoleon III, strengthened the resistance in Congress, which coalesced round vice-president Peixoto, and soured public opinion. This also caused republicans of the South to withdraw their support from the marshal and provisional government. The situation approached a climax when Fonseca dissolved the National Congress and declared a 'state of emergency,' November 3, 1891. A group of deputies opposed this decision and found support among the high-ranked officers of the Navy including Admiral Custódio José de Melo. The marshal found himself on the brink of a civil war. On November 23, 1891 he signed a resignation (to no one in particular) and turned over the presidency to Floriano Peixoto.

Deodoro da Fonseca died in Rio de Janeiro on August 23, 1892.