Paulo Dias de Novais era nieto, por vía paterna, del navegante Bartolomeu Dias, y fue escrivão de la Hacienda Real y fidalgo de la Casa Real.
Novais obtuvo del rey D. Sebastião (1568-1578) una Carta de Donación (1571), que le dio el título de «Governador e Capitão-Mor, conquistador e povoador do Reyno de Sebaste na Conquista da Etiópia ou Guiné Inferior», nombre con el que se conocía entonces la región de Angola.
[2] Ya había unas siete poblados y Novais encontró siete embarcaciones fondeadas y cerca de cuarenta portugueses establecidos, enriquecidos con el comercio de esclavos, refugiados allí de los jagas.
Se cree que ya llevaban allí establecidos desde hacía algunos años, ya que en la isla también había una iglesia y un sacerdote.
Bajo los términos de la Carta de Donación recibida, Novais debía de ampliar el territorio al norte a orillas del río Dande (Bengo), hacia el sur, y hacia el interior a lo largo del curso del río Cuanza.