Il naquit en 1612, à Neuville-sur-Vannes (Aube, en France). Dès l'âge de 13 ans, il devint militaire (de formation). En 1640, la Société Notre-Dame, ayant acquit l'île de Montréal qui appartenait à la Compagnie des Cent-Associés, se cherchait un chef pour diriger l'expédition qui se rendrait sur cette île dans le but de convertir les Amérindiens. Jérôme Le Royer de la Dauversière, sous les conseils du père Charles Lallemant, demanda à Maisonneuve qui accepta ce poste.
           Au printemps 1641, il prit donc la route vers La Rochelle (port de la France) où devait avoir lieu le départ vers la Nouvelle-France. Deux navires quittèrent le port: Jeanne Mance était dans l'un d'eux et arriva à Québec le 8 août 1641. Le bateau de Maisonneuve, cependant, arriva le 20 septembre 1641 à Tadoussac. Ils furent forcés à demeurer à Québec pour la saison hivernale, car il était trop tard pour penser se rendre à Montréal. Charles Huault de Montmagny tenta alors de convaincre Maisonneuve que l'île d'Orléans représentait en un meilleur endroit pour établir un poste, mais Maisonneuve rétorqua que sa mission consistait à aller à Montréal, et non pas de choisir le lieu du poste de traite. Il fit d'ailleurs honneur à sa parole dès le printemps suivant...
           Dès que les glaces ne contrent plus le fleuve Saint-Laurent, Paul Chomedey de Maisonneuve ordonna qu'on se rende à Montréal. Le 8 mai 1642, Maisonneuve, Jeanne Mance, le gouverneur Montmagny, les pères jésuites, les futurs habitants de Ville-Marie (nom donné à l'établissement sur l'île de Montréal le 27 février 1641 par la Société de Notre-Dame de Montréal, à Paris) et plusieurs autres partirent en direction de l'île de Montréal... Ils y débarquèrent le 17 mai 1642, après 9 jours de navigation... Rapidement, Maisonneuve y fit construire un petit fort. Puis, à l'automne de la même année, Jeanne Mance fonda l'Hôtel-Dieu, le premier hôpital de Montréal. Elle décédera dans cette même ville en 1673 (alors âgée d'environ 67 ans).
           Un événement marqua l'histoire de Montréal, au cours de l'année de sa fondation, en 1642. En effet, au jour de Noël de cette année, le fleuve Saint-Laurent menaça d'inonder le poste de traite de Ville-Marie. Maisonneuve promit alors qu'il planterait une croix sur la montagne si les eaux se retiraient... Ce fut d'ailleurs ce qui arriva, et Maisonneuve, tenant sa promesse, transporta lui-même la croix qui fut érigée au sommet de l'actuel Mont-Royal.
           Par la suite, Maisonneuve gouverna Ville-Marie qui devint rapidement le principal poste de traite de la colonie grâce à sa position stratégique qui contrebalançait avec les nombreuses guerres iroquoises. Le fondateur de l'actuelle ville de Montréal occupa d'ailleurs ce poste de gouverneur jusqu'à ce qu'il revienne en France, en 1665. Il décéda finalement dans la belle ville parisienne en 1676.