"It is said that when the first Portuguese arrived in Luanda sometime during the 16th century, they first met some local fishermen on the beach of Ilha. When they asked 'what is the name of this place?' whilst pointing to the ground, the fishermen's answer was "Luanda," which actually means 'fishing basket'."

The history of Luanda is very long, and to an extent, quite complicated. In fact, Luanda is the oldest European city in Africa south of Sahara. The above quote is one explanation of how Luanda got it's name, another explanation is that the city of Luanda is named after the African word Loanda which means "flat land." Yet, another theory assumes that the name Luanda is, like previously, derived from the African word Loanda, which was the name of a group of people who lived in these lands prior to the construction of a city. (In fact, the Loanda people existed and were semi-independent but paying taxes to the Manikongo of Kongo)

The city of Luanda was started in 1575, on February 20, when Paulo Dias de Novais landed with seven ships, 400 soldiers and 100 families on the Ilha de Luanda. It was not, however, until the next year, when the Portuguese settlers moved across the bay of Luanda, that the city of São Paulo de Loanda was really started and in 1605 the town was granted the status of a city. This makes Luanda the first city to be founded by Europeans in sub-Saharan Africa.

By this time, Luanda contained, among some administrative buildings and private housing, a Cathedral and a Jesuit Church. Luanda had also already a good economy based in slave trade. This, however, attracted the Dutch who controlled the area from 1641 to 1648 when Salvador Correa de Sa conquered the lands back. To celebrate the victory, the name of the city was changed to São Paulo da Assuncao and a few years after, a large area was granted Commandor de Sa for his military achievements.

During the later half of the 1600's, the Portuguese worked with the construction of Luanda and by the end of this century, Luanda was a well planned town with two parts: The Citade Alta where the upper-class, the colonial power and the Church was based and the lower areas where traders and pombeiros (people who captured slaves for a living) had based their homes and business. Not only white men lived in Luanda, many native Africans had houses and apartments here too.

In 1779, the two parts of Luanda were linked by paved roads, after the construction of paved roads had begun under the rule of Sousa Coutinho. The period under Governor Coutinho also brought many new public buildings to Luanda.