L’île, d’abord concédée en seigneurie à Jean de Lauson, est acquise en 1640 par la société, qui la conserve jusqu’en 1663. Le Royer de La Dauversière choisit un jeune officier, Paul de Chomedey de Maisonneuve, pour gouverner la nouvelle colonie et une infirmière, Jeanne Mance, pour y fonder un hôpital. Une quarantaine de colons partent de La Rochelle, en France, le 9 mai 1641. Arrivés à Québec trop tard à l’automne pour pouvoir poursuivre leur route jusqu’à Montréal, ils passent l’hiver à Sillery (Québec). Malgré les efforts du gouverneur Charles Huault de Montmagny, qui tente de dissuader Maisonneuve de mettre son projet à exécution, l’expédition part pour Montréal le 8 mai 1642. Les colons, Montmagny, quelques missionnaires jésuites et Maisonneuve arrivent sur le site le 17 mai, à proximité de l’ancien village iroquois d’Hochelaga. Maisonneuve prend officiellement possession de l’île au nom de la Société de Notre-Dame de Montréal. Une messe est célébrée le lendemain et le nouvel établissement, dédié à la Vierge Marie, prend le nom de Ville-Marie, nom utilisé pendant une dizaine d’années avant d’être remplacé par Montréal. Rapidement, les colons se consacrent à la construction d’une clôture, d’une résidence pour le nouveau gouverneur et de quelques habitations. Sous la supervision de Jeanne Mance, l’Hôtel-Dieu de Montréal est érigé à l’automne.
En tant que poste le plus reculé de la Nouvelle-France, Ville-Marie se retrouve au cœur du réseau de communication donnant accès à l'Iroquoisie et à la Huronie. Sa position est stratégique tant au niveau militaire que commercial. La colonie devient un poste important pour le commerce des fourrures. Elle connaît toutefois des débuts difficiles en raison des attaques répétées des Iroquois. En 1645, Maisonneuve fait construire un fort et, huit ans plus tard, il engage en France une centaine de colons-soldats au cours de la Grande Recrue. L’arrivée de cette force défensive permet au jeune établissement de résister aux attaques iroquoises quoique sa sécurité ne soit définitivement assurée qu’avec la Grande Paix de Montréal en 1701.