Many controversies mark the archipelago's discovery. Its original name, Ilha da Quaresma (Lent Island), it is known to have been sighted by expeditions from the years 1501, 1502 and 1503. The Viscount of Santarém, however, attributed the discovery to Gaspar de Lemos, captain of the supply ship of Pedro Álvares Cabral's fleet, sent back to Portugal with news of the discovery of Brazil. Modern historians, however, attribut the discovery of the archipelago to the 1501-1502 expedition led by Fernao de Noronha.

The first to actually describe the island was Amerigo Vespucci, who travelled with a Portuguese expedition to Brazil in the year 1503. In 1534, the Fernando de Noronha Archipelago was invaded by the English, and from 1556 until 1612, it was held by the French. In 1628, it was invaded by the Dutch, who were displaced two years later by a Spanish-Portuguese military expedition led by Rui Calaza Borges. The Dutch occupied the island once again in 1635, making it a hospital for its troops which occupied Northeastern Brazil. The island became known as Pavonia, in honor of Michiel de Pauw, one of the directors of the Dutch West Indies Company. It would remain under Dutch control for nearly twenty years, when it was reconquered by Portugal.

Finding it uninhabited and completely abandoned in 1736, the French East Indies Company took the island and renamed it Isle Dauphine. Only from 1737 on, after the expulsion of the French, Fernando de Noronha was definitively occupied by Portugal. This time Portugal decided to fortify the island. For this purpose, ten forts were built in all strategic points where a possibility of disembarkation existed. Nine in the main island and one in the Ilha de Sao José situated in front of the Saint Anthony harbour. All the forts were connected by a network of stone roads. The defence system was planned by the Portuguese militar engineer Diogo da Sylveira Vellozo. Around 1770, the first permanent settlement, Vila dos Remédios, was founded. The village was divided in two unities (pátios), in the superior were the administrative buildings in the other was the church and the religious buildings.

As Brazil became independent, very little changed for Fernando de Noronha.

At the beginning of the 20th century, the English arrived to provide technical cooperation in telegraphy (The South American Company). Later the French came with the French Cable and the Italians with Intalcable. In 1942, during World War II, the archipelago was made a Federal Territory that also included Rocas Atoll and Saint Peter and Paul Rocks, and political and ordinary prisoners were sent to the local prison. In 1988 approximately 70% of the archipelago was declared a national park, with the goal of preserving the land and sea environment. On October 5, 1988, the Federal Territory was dissolved and added to the state of Pernambuco (except Rocas Atoll, which was added to the state of Rio Grande do Norte