In the 1460s, Estêvão was a knight in the household of the royal prince Infante Ferdinand, Duke of Viseu, and, at some point, entered the military Order of Santiago.
Upon ascending to the throne as King John II of Portugal in 1481, the Order's fortunes - and Estêvão da Gama's - rose with him.
After Bartolomeu Dias doubled the Cape of Good Hope in 1488, Estêvão da Gama was appointed by John II to lead the first sea expedition from Portugal to India (at least according to chroniclers Barros and Castanheda).
At the death of John II in 1495, Estêvão da Gama and his sons remained part of the opposition party gathered around D. Jorge in Palmela, against King Manuel I.
The new king resurrected John II's plans for the India expedition, and the appointment was, once again, to go to Estêvão da Gama, as had been earlier promised.