A cidade ganha o nome através da sua ilha (Ilha de Luanda), local onde os primeiros colonos portugueses se radicaram.[8] O topónimo Luanda provém do étimo lu-ndandu. O prefixo lu, primitivamente uma das formas do plural nas línguas bantas, é comum nos nomes de zonas do litoral, de bacias de rios ou de regiões alagadas (exemplos: Luena, Lucala, Lobito) e, neste caso, refere-se à restinga rodeada pelo mar. Ndandu significa valor ou objecto de comércio e alude à exploração dos pequenos búzios colhidos na ilha de Luanda e que constituíam a moeda corrente no antigo Reino do Congo e reino do Ndongo em grande parte da costa ocidental africana, conhecidos por zimbo ou njimbo.[9]
Como os povos ambundos moldavam a pronúncia da toponímia das várias regiões ao seu modo de falar, eliminando alguns sons quando estes não alteravam o significado do vocábulo, de Lu-ndandu passou-se a Lu-andu. O vocábulo, no processo de aportuguesamento, passou a ser feminino, uma vez que se referia a uma ilha, e resultou em Luanda.[9]
Outra versão para a origem do nome refere que o mesmo deriva de "Axiluandas" (homens do mar), nome dado pelos portugueses aos habitantes da ilha, porque quando aí chegaram e lhes perguntaram o que estavam a fazer, estes responderam "uwanda", um vocábulo que em quimbundo designava trabalhar com redes de pesca.[10]
Quando os portugueses chegaram à região onde hoje se localiza a cidade de Luanda, esta era parte integrante do reino do Ndongo, tributário do reino do Congo, na altura e era especialmente importante por ser uma zona produtora de nzimbo, uma pequena concha com valor fiduciário.[11]
Respondendo a um pedido de envio de missionários feito aos portugueses pelo rei Ndambi a Ngola do Ndongo em 1557, no dia 22 de Dezembro de 1559 zarparam de Lisboa três navios com um emissário do rei de Portugal, Paulo Dias de Novais, e dois padres jesuítas, Francisco de Gouveia e Agostinho de Lacerda. Chegados à barra do Cuanza no dia 3 de maio de 1560, a missão portuguesa foi recebida com hostilidade e desconfiança pelo novo rei do Ndongo, Ngola Kiluanje kia Ndambi, que os encarou como agentes do rei do Congo, mandando-os aprisionar. Mais tarde, com a promessa de conseguir apoio diplomático e militar português, Paulo Dias de Novais teve permissão para regressar a Portugal.[12]
Na sua segunda viagem a esta região, Paulo Dias de Novais partiu de Lisboa no dia 23 de Setembro de 1574, acompanhado por mais dois padres da Companhia de Jesus, tendo chegado à Ilha de Luanda em Fevereiro de 1575,[12] aportando com dois galeões, duas caravelas, dois patachos e uma galeota.[13] Aí estabeleceu o primeiro núcleo de colonos portugueses: cerca de 700 pessoas, onde se encontravam religiosos, mercadores e funcionários, bem como 350 homens de armas.[14]
A Ngola Kiluanje kia Ndambi tinha entretanto sucedido a Njinga Ngola Kilombo kia Kasenda, discípulo do padre Francisco de Gouveia que, na sua estadia forçada de dezena e meia de anos, tinha aproveitado para fazer a sua acção evangelizadora entre os angolanos. No dia 29 de Junho de 1575 , Paulo Dias de Novais recebeu uma comitiva enviada pelo ngola para o saudar.[12]
Reconhecendo não ser a ilha de Luanda o lugar mais adequado, avançou para terra firme e fundou a vila de São Paulo de Loanda em 25 de Janeiro de 1576, tendo lançado a primeira pedra para a edificação da igreja dedicada a São Sebastião — santo de grande devoção dos portugueses e patrono onomástico do rei de Portugal[12] —, no lugar onde é hoje o Museu das Forças Armadas.[1]
A escolha do novo local para a vila foi influenciada sobremaneira pela existência de um magnífico porto natural, situado numa baía protegida por uma ilha; de uma fonte de água potável, as águas do poço da Maianga na (então) lagoa dos Elefantes;[15] e das excelentes condições de defesa oferecidas pelo morro de São Paulo, após a reconquista do lugar aos neerlandeses designado por morro de São Miguel, após a dedicação do forte que aí existe a São Miguel, santo da devoção de Salvador Correia de Sá.[16] A população constituída pela comitiva de Paulo Dias de Novais, composta por sapateiros, alfaiates, pedreiros, cabouqueiros, taipeiros, um físico e um barbeiro, teve dificuldades de adaptação à inclemência do clima e à carência de condições para a fixação.[11] No entanto, a vila expandiu-se para a "Cidade Alta", na continuação do morro de São Paulo, onde se construíram as instalações para a administração civil e religiosa. Os soldados e os mercadores de escravos viviam na "Cidade Baixa", na área actual dos Coqueiros.[15]