Em “taipa e area solta”, esta primitiva estrutura foi arrasada durante o governo de André de Albuquerque por um ataque combinado de corsários francesas e indígenas (1591), foi reconstruído a partir do ano seguinte, em alvenaria de pedra e cal.
Foi concluído em 1597 sob a invocação de Santa Catarina de Alexandria, padroeira da Capela do forte, e em homenagem a Dona Catarina de Portugal, Duquesa de Bragança. Nesse mesmo ano, uma esquadra de treze navios franceses desembarcou uma força de 350 homens, que atacaram o forte por terra (SOUZA, 1885:78).
Durante a resistência ao assalto registrou-se a morte do comandante do forte, reassumindo o comando o Capitão João de Matos Cardoso (BARRETTO, 1958:114-115).
Em 1601 a sua guarnição era de um capitão comandante, um alferes, um sargento, um tambor, e vinte soldados armados com mosquetes; estava artilhado com três peças de bronze e nove de ferro.
Em 1611, as peças de bronze foram refundidas em Pernambuco, e no ano seguinte, o seu efetivo era de 300 soldados armados com arcabuzes, a sua artilharia montando a onze peças (BARRETTO, 1958:116-117).