In 1498, during Vasco da Gama's visit to India, the local Kolathiri king granted the land to Portuguese to build a settlement in present-day Kerala.

The construction activity began the very next day, on 24 October 1505, when Goncalo Gil Barbosa - the Portuguese factor of Cannanore (Kannur) - laid the foundation stone.

The construction of the wooden fort was completed on 30 October 1505: its first Captain was Lourenco Britto, who led a garrison of 150 Portuguese men, and controlled two ships in the sea.

In August 1509 Almeida, refusing to recognize Afonso de Albuquerque's as the new Portuguese governor to supersede himself, arrested him in this fortress after having fought the naval Battle of Diu.

Afonso de Albuquerque was released after six months' confinement and become governor on the arrival of the grand-marshal of Portugal with a large fleet, in October 1509.