Suivant l'usage à cette époque de fervente piété lorsqu'on commençait quelque grande entreprise, Cartier et ses compagnons implorèrent, avant de s'embarquer, l'aide et la protection du maître de toutes choses. Ils se rendirent en corps à la cathédrale de St.-Malo, où, après avoir assisté à une messe solennelle et communié très-dévotement, l'évêque, revêtu de ses habits pontificaux et entouré de son clergé, leur donna sa bénédiction qu'ils reçurent tous avec un pieux recueillement.
L'escadre portant 110 hommes et des provisions pour un long voyage, ouvrit enfin, après quelques jours d'attente, ses voiles à un vent favorable dans le mois de mai (1535). Elle se composait de la Grande-Hermine de 100 à 120 tonneaux, sur laquelle Cartier arbora son pavillon, comme capitaine général; de la Petite-Hermine et de l'Émerillon, commandés, l'un par Guillaume Le Breton, et l'autre par Marc Jalobert. Plusieurs gentilshommes servaient à bord en qualité de volontaires. Dans la traversée qui fut longue, la petite flotte fut dispersée par les vents. Cartier n'arriva qu'en juillet dans la baie des Châteaux, dans une île située entre Terreneuve et Labrador, qu'il avait donnée pour rendez-vous; et les deux autres bâtimens que 10 jours après.
Le capitaine français entra dans le fleuve du Canada par le nord de l'île d'Anticosti. Il s'arrêta quelque temps dans une baie que l'on suppose être l'embouchure de la rivière St. Jean, et à laquelle il donna le nom de St.-Laurent, appellation qui s'est étendue dans la suite à ce fleuve et au golfe dans lequel il se jette.
Conduit par ses deux Sauvages qu'il avait ramenés avec lui, il le remonta plus de 200 lieues à partir de l'Océan, jusqu'au pied d'un île agréablement située (l'île d'Orléans). Selon leur rapport ce pays se divisait en trois provinces. Le Saguenay s'étendait depuis l'île d'Anticosti jusqu'à l'île aux Coudres. Le Canada, dont la principale bourgade était Stadaconé (Québec), commençait à cette dernière île et se prolongeait en remontant le fleuve jusque vers Hochelaga, qui formait la dernière province et la portion la plus riche et la plus populeuse de toute la contrée.
Le nom de Canada, donné ici par les Indigènes à une partie du pays à la totalité duquel il s'étend maintenant, ne permet point d'avoir de doutes sur son étymologie. L'on doit donc rejeter les hypothèses de ceux qui veulent lui donner une origine européenne. L'on sait du reste que ce mot signifie, en dialecte indien, amas de cabanes, village.
Cartier fit mettre alors ses guides à terre pour s'aboucher avec les naturels, qu'il vit bientôt s'approcher de ses navires dans de nombreux canots d'écorce, et offrir aux Français des poissons, du maïs et des fruits: il les reçut avec politesse et leur fit distribuer des présens.
Le lendemain, l'Agouhanna, ou chef du pays, qui résidait à Stadaconé, descendit avec douze canots pour visiter les étrangers qui entraient sur le territoire de la tribu. L'entrevue fut amicale; et les Européens et les Sauvages se séparèrent fort contens les uns des autres. Avant de partir le chef indien demanda la permission de baiser les bras du capitaine français; ce qui était une des plus grandes marques de respect chez ces peuples.
Cependant, ce dernier, après avoir reconnu le fleuve jusqu'au bassin de Québec, voyant la saison avancée, prit la résolution hardie d'y passer l'hiver. En conséquence, il fit monter ses vaisseaux dans la rivière St.-Charles, nommée par lui, Ste.-Croix, sous la bourgade de Stadaconé qui couronnait une montagne du côté du sud, pour les mettre en hivernage. Cet endroit du St.-Laurent est, à cause de ses points de vue, l'un des sites les plus grandioses et les plus magnifiques de l'Amérique.
Les deux rives du fleuve depuis le golfe ont un aspect imposant, mais triste. Sa grande largeur à son embouchure, quatre vingt dix milles, les dangers de ses nombreux écueils et ses brouillards en en faisant un lieu redoutable pour les navigateurs, contribuent encore à augmenter cette tristesse. Les côtes escarpées qui le bordent pendant l'espace de plus de cent lieues; les montagnes couvertes de sapin noir, qui resserrent au nord et au sud la vallée qu'il descend et dont il occupe par endroit presque tout le fond; les îles aussi nombreuses et variées par leur forme, que dangereuses aux marins, et dont la multitude augmente à mesure qu'on avance; enfin tous ces débris épars des obstacles qu'il a rompus et renversés pour se frayer un passage à la mer, saisissent l'imagination du voyageur qui le remonte pour la première fois autant par leur majesté que par la solitude profonde qui y règne.
Mais à Québec la scène change. Autant la nature est âpre et sauvage sur le bas du fleuve, autant elle est ici variée et pittoresque, sans cesser de conserver un caractère de grandeur.