De nouvelles difficultés, suscitées «par quelques brouillons, qui n'avaient cependant aucun intérêt en l'affaire,» retardèrent tellement la publication du privilège et des règlements de la nouvelle association, qu'il fut impossible à Champlain de rien faire encore cette année (1613) pour l'habitation de Québec, «dans laquelle il désirait mettre desxxxvii ouvriers pour la réparer et l'augmenter.» De sorte, qu'il fallut, pour le moment, se contenter de passeports, que le prince donna pour quatre vaisseaux prêts à faire voile, lesquels s'engageaient à fournir chacun quatre hommes pour la continuation des découvertes.
Le voyage de 1613 fut pour l'auteur une déception, quoiqu'il n'ait pas été un des moins utiles. Champlain eut un moment l'espoir de trouver enfin le fameux passage du Nord-Ouest tant cherché par tous les navigateurs.
Un de ceux qui étaient retournés du Canada en 1612, nommé Nicolas de Vignau, lui assura que le lac où l'Outaouais prenait sa source, se déchargeait dans la mer du Nord, sur le rivage de laquelle il disait avoir vu de ses propres yeux les débris d'un vaisseau et les chevelures de quatre-vingts anglais qui formaient l'équipage. Ce récit paraissait d'autant plus vraisemblable, que les Anglais avaient tout récemment poussé leurs courses aventureuses jusque dans les profondeurs de la baie d'Hudson. Le chancelier de Sillery, le maréchal de Brissac, le président Jeannin et autres personnes graves, furent d'avis que Champlain ne devait pas négliger de voir la chose en personne.
Il partit donc de l'île Sainte-Hélène le 27 de mai 1613 avec quatre français et un sauvage, et remonta l'Outaouais jusqu'à la résidence de Tessouat, chef des Algonquins de l'isle, c'est-à-dire jusqu'à l'île des Allumettes. Tessouat, qui avait déjà fait la connaissance de l'auteur les années précédentes, reçut cette visite inattendue et inespéréexxxviii avec toutes les marques de la plus vive satisfaction. Il prépara un grand festin, pour souhaiter la bienvenue à ces hôtes extraordinaires. Tous les principaux chefs devaient s'y trouver, et là Champlain leur ferait connaître ses intentions et le but de son voyage.
Le repas fini, il fallut, suivant la coutume, fumer le calumet pendant une demi-heure, après quoi, Champlain leur exposa, qu'il était venu d'abord pour les visiter et lier avec eux une amitié encore plus durable, mais aussi pour leur demander ce qu'ils lui avaient déjà promis, c'est-à-dire, de lui faciliter le voyage de la mer du Nord, que de Vignau prétendait avoir vue l'année précédente.
De Vignau, qui n'avait jamais été plus loin que la cabane de Tessouat, ne pouvait plus échapper à une conviction des plus humiliantes et des plus terribles. Tessouat et les autres capitaines, indignés d'une si impudente imposture, s'écrièrent «qu'il le fallait faire mourir, ou qu'il dît celui avec lequel il y avait été, et qu'il déclarât les lacs, rivières et chemins par lesquels il avait passé.» De Vignau n'avait garde d'accepter un pareil défi, il avait toujours compté que les difficultés incroyables d'un pareil voyage effraieraient Champlain, où qu'enfin quelque obstacle insurmontable finirait par lasser son courage, et qu'ainsi, après avoir fait sans dépense le voyage du Canada, il n'en toucherait pas moins la récompense promise à sa prétendue découverte.
«Après avoir songé à lui,» il se jeta à genouxxxxix aux pieds de Champlain, et demanda son pardon. «Ainsi transporté de colère, dit l'auteur, je le fis retirer, ne le pouvant plus endurer devant moi.» Les Algonquins voulaient absolument en faire bonne justice, et, si Champlain ne leur eût défendu de lui faire aucun mal, ils l'eussent infailliblement mis en pièces.
Cette expédition, quoique manquée dans son objet principal, eut néanmoins un excellent résultat. Tous ces peuples, l'année précédente, avaient été si mécontents des traiteurs, qu'ils avaient pris la résolution de ne plus descendre; et il fallut tout l'ascendant que Champlain avait sur eux pour les ramener à de meilleures dispositions.
De retour en France, Champlain s'occupa de mener à bonne fin les négociations qui n'avaient pu se terminer avant le départ des vaisseaux, et réussit enfin à former une puissante compagnie, qui devait se composer des marchands de Saint-Malo, de Rouen et de la Rochelle; mais les Rochelois furent si longtemps à accepter les conditions, qu'on les laissa de côté; les Normands et les Bretons «prirent l'affaire moitié par moitié.»
A peine cette société des marchands était-elle formée, que quelques malouins incommodes, fâchés de ne s'être pas présentés à temps, et ne pouvant contester les droits de la compagnie, eurent l'adresse de faire insérer «au cahier général des états» un article demandant que la traite fût libre pour toute la province. Champlain, voyant encore sur le point d'échouer un projet qui semblait promettre un meilleur avenir à sa chère colonie, alla trouverxl le prince de Condé, et lui représenta l'intérêt qu'il avait à ne point laisser annuler un privilège aussi nécessaire. Il plaida si bien la cause, que la société fut maintenue dans ses droits.