Alvise was born at the Ca' da Mosto, a palace on the Grand Canal of Venice from which his name derives. His father was Giovanni da Mosto, a Venetian civil servant and merchant, and his mother Elizabeth Querini, from a leading patrician family of Venice. Alvise was the eldest of three sons, having younger brothers Pietro and Antonio.
At a remarkably young age, Cadamosto cast out as a merchant adventurer, sailing with Venetian galleys in the Mediterranean. From 1442 to 1448, Alvise undertook various trips on Venetian galleys to the Barbary Coast and Crete, as a commercial agent of his cousin, Andrea Barbarigo. In 1451, he was appointed noble officer of the marine corps of crossbowmen on a galley to Alexandria. The next year, he served the same position on a Venetian galley to Flanders. Upon his return, he found his family disgraced and dispossessed. His father, caught in a bribery scandal, had been banished from Venice, and taken refuge in the Duchy of Modena. His Querini relatives took the opportunity to seize possession of his family's property. This setback marred the future prospects of Cadamosto's career in Venice, and probably encouraged his spirit of adventure, hoping to restore his family name and fortune by great feats of his own.