On the accession of John II. to the throne of Portugal in 1481, the discoveries along the coast of Africa were resumed with a new spirit.  While infante or hereditary prince, his principal revenue was derived from the profits of the Guinea trade, and of the importation of gold from the haven of Mina; and among the first measures of his reign, he turned his attention to the improvement and extension of that valuable branch of commerce.  For this purpose, he gave orders to make all necessary preparations for building a fortress and church at the port of Mina.  All the requisite materials, even to stones and tiles, were accordingly shipped from Lisbon in a squadron of ten caravels and two transports, with 500 soldiers and 200 labourers or workmen of various kinds.  This expedition was placed under the command of Don Diego d’Azumbuja, an experienced officer, under whom were the following naval captains, Goncalez da Fonseca, Ruy d’Oliveira, Juan Rodrigues Gante, Juan Alfonso, Diego Rodrigues Inglez, Bartholomew Diaz, Pedro d’Evora, and Gomez Aires.  This last was a gentleman belonging to the household of Pedro king of Arragon, all the others being noblemen of the household of King John.  Pedro de Cintra and Fernam d’Alfonso commanded the transports, and a small vessel attended the squadron as an advice-boat.  This squadron sailed on the 11th December 1481, and reached their destination on the 19th January 1482, at an African village named Aldea, where they found Juan Bernardo, who had previously sailed for the coast in quest of gold.

Bernardo was immediately sent by Azumbuja, to inform Camaranca, the Negro chief of the district, with the arrival of the Portuguese armament, and to desire a conference, with directions to endeavour to impress that chief with a high sense of the rank and character of the Portuguese officers, and of the irresistible power of the armament now upon his coast.  Early next morning, Azambuja landed with all his followers, who were secretly armed, in case of meeting with any hostilities from the natives; and moved forwards in great form to a large tree, not far from the Negro village of Aldea, on a spot which had been chosen as a convenient situation for the intended fortress.  A flag, bearing the royal arms of Portugal, was immediately displayed upon the tree, and an altar was placed under the shade of its boughs, at which the whole company united in assisting at the first mass that was celebrated in Guinea, offering up their solemn prayers to God for the speedy conversion of the idolatrous natives, and for the perpetual continuance and prosperity of the church which was to be erected on this spot.  The day on which this impressive ceremony was performed being dedicated to St Sebastian, that name was given to the valley on which the tree stood, under which they were now assembled.