Cartier est déjà un marin expérimenté lorsque François Ier fait appel à lui, mais on ignore tout de ses débuts. On sait qu'il est recommandé au roi de France par Jean Le Veneur, brillant prélat qui vient d'obtenir du pape une interprétation laxiste de la bulle de 1493, partageant le monde entre l'Espagne et le Portugal. Dès lors, François Ier estime avoir les mains libres pour effectuer des voyages de découvertes dans des régions qui ne sont pas encore fréquentées par les Ibériques. Il prête d'abord une oreille attentive aux dires du navigateur italien Verrazano, certifiant l'existence d'un passage par le nord pour atteindre les Indes et le Cathay (la Chine), ce qui pourrait assurer une nouvelle route vers l'or et les épices. Verrazano part en reconnaissance en 1524, longe l'Amérique du Nord, et revient en France en passant par Terre-Neuve. Puis, Cartier est chargé d'aller vers les terres inconnues situées au-delà du détroit de Belle-Isle, entre le Labrador et Terre-Neuve. Le but essentiel est la découverte de grandes quantités d'or « et autres riches choses ». Mais il était possible, aussi, que la découverte le conduise vers l'Orient.
Parti avec deux navires le 20 avril 1534, le Malouin traverse l'Océan en 20 jours, franchit le détroit de Belle-Isle, puis, vers le sud, gagne les îles de la Madeleine et celles qui porteront le nom de Prince-Édouard. Il prend possession du littoral continental en érigeant une croix sur les falaises de la baie de Gaspé (24 juillet). Il revient à Saint-Malo le 5 septembre. Les récits de deux indigènes ramenés en France évoqueront les richesses des terres encore à découvrir. Encouragé, François Ier confie trois navires à Cartier pour une nouvelle expédition, plus minutieuse. On met à la voile le 19 mai 1535. Au-delà de Terre-Neuve, la voie maritime vers le « Cathay » de Marco Polo semble découverte lorsque se révèle l'immense estuaire du Saint-Laurent. Le 14 septembre, les Français s'établissent au havre Sainte-Croix, près du village indien de Stadaconé et du site de Québec. Poursuivant vers l'amont, Cartier parvient ensuite, avec deux chaloupes, à Hochelaga, gros village indien au pied des hauteurs sur lesquelles se construira Montréal. Les rapides de « Lachine », qui évoquent toujours la quête d'un Orient fabuleux, arrêtent l'exploration. Après un dur hivernage à Stadaconé, où le scorbut fait de nombreuses victimes, Cartier part le 6 mai 1536 et passe au sud de Terre-Neuve, dont il prouve ainsi l'insularité. Il arrive le 16 juillet à Saint-Malo.
François Ier, auquel le rapport de son explorateur laisse espérer la découverte de grandes richesses minières, est satisfait de l'entreprise. Toutefois, le nouveau conflit avec Charles Quint va empêcher d'y donner suite dans l'immédiat. La période d'attente qui commence est capitale pour l'histoire coloniale de la France. C'est alors, en effet, que, face aux prétentions de l'Empereur et de la cour de Lisbonne sur l'ensemble de l'Amérique, François Ier précise sa doctrine concernant l'expansion outre-mer, établissant le principe de la légitimité des prises de possession basées sur l'occupation effective, et la mise en valeur des terres nouvelles qui ne sont fréquentées ni par les Espagnols ni par les Portugais.
À la tête d'une entreprise qui prend une nouvelle dimension, il faut désormais un personnage important, un noble : Jean-François de La Roque de Roberval sera donc le lieutenant général des terres nouvelles. Avec 5 navires, en 1541, Cartier précède son chef et établit un camp en amont du site de Québec, le 23 août. Il commence aussitôt la mise en valeur des terres. Une nouvelle exploration vers l'amont, au-delà d'Hochelaga, est encore interrompue par les rapides. Mais Cartier a trouvé des cailloux et des rochers aux reflets brillants, sans doute des diamants et des pépites… L'hivernage est rude et marqué par divers excès à l'encontre des Indiens, qui commencent à se montrer hostiles. Sans attendre Roberval, Cartier entreprend de repartir. Il rencontre enfin son chef à Terre-Neuve mais, pressé de montrer ses trésors, le Malouin refuse de rester en Amérique. Au retour, ses richesses s'avèrent n'être que des roches sans aucune valeur… La cruelle désillusion qui en résulte va condamner pour un temps les entreprises en direction de la « Nouvelle-France ».