No tempo do capitão-mor Paulo Dias de Novais (neto do navegador português Bartolomeu Dias e fundador da cidade de Luanda) passara cerca de um século sobre a viagem pioneira de Diogo Cão.
Os Portugueses deparavam, agora, com a resistência militar do senhor do Ndongo, Ngola Kiluanje. A meio do ano de 1585 o rei Ngola Kiluanje acedeu ao pedido de um súbdito audacioso, Ndala Kitunga, que se lhe ofereceu para conduzir um exército do Ndongo contra as forças do português Novais.
Kitunga era um ambundo cristianizado que, por razões ignoradas, resolvera desligar-se dos protectores europeus. Kiluanje colocou à sua disposição um efectivo numeroso e, além do armamento tradicional, forneceu-lhe pólvora e armas de fogo. Depois lançou-o no encalço do inimigo.
Ngola Kiluanji resiste à ocupação portuguesa até a sua morte. No entanto, uma parte do território é tomada, constituindo o primeiro espaço colonial na região. O rei Kiluanji refugia-se em Cabassa, no interior de Matamba, e consegue reter o avanço dos portugueses. Após a morte de Kiluanji sucede seu filho Ngola Mbandi, meio irmão de Nzinga.
Os portugueses há algum tempo traficando com os jagas do litoral, guerreiros vindos do leste, também conhecidos por imbangalas, estão agora impedidos de fazê-lo, pois a rota para o interior é controlada pelo Ngola Mbandi. Este envia sua irmã Nzinga a Luanda para negociar com os portugueses. Recebida em Luanda com grande pompa pelo governador geral ela negocia sem ceder algum território e pede a devolução de territórios que obtém pela sua conversão política ao cristianismo, recebendo o nome de Dona Anna de Sousa. Mais tarde suas irmãs Cambi e Fungi também se convertem, passando a se chamar Dona Bárbara e Dona Garcia respectivamente.
Os portugueses, no desejo de estabelecerem o comércio com o jaga de Cassanje no interior, não respeitam o tratado de paz. A rebelião de alguns sobas (chefes), que se aliam ao jaga de Cassange e aos portugueses, cria uma situação de desordem no reino de Ngola.
Nzinga, ao encontrar um dos sobas, seu tio, que se dirigia a Luanda para se submeter aos portugueses, manda decapitá-lo, e dando conta da 
hesitação de seu irmão manda envenená-lo abrindo assim caminho ao poder e ao comando da resistência à ocupação das terras de Ngola e Matamba.
Os portugueses elegem um chefe mbundu, Aiidi Kiluanji (Kiluanji II), como novo Ngola das terras do Ndongo.
Nzinga, não conseguindo a paz com os portugueses em troca de seu reconhecimento como rainha de Matamba, renega a fé católica e se alia aos guerreiros jagas de Oeste se fazendo iniciar nos ritos da máquina de guerra que constituía o quilombo.