Ungefähr 8.000 Jahre lang besiedelten Huronen, Algonquin und Irokesen die Gegend rund um Montreal. Der erste Europäer, der auf die „Île de Montréal“ gelangte, war im Jahre 1535 der französische Entdecker Jacques Cartier. Dort befand sich ein Indianerdorf namens Hochelaga. Er war dort hin gereist, weil er hörte, es gebe Gold auf der Insel. Doch er fand nur falsches Gold, wahrscheinlich Pyrit. Cartier gab dem sich in unmittelbarer Nähe des indianischen Dorfes erhebenden Berg den Namen Mont Réal, königlicher Berg, und schuf damit die Grundlage für die spätere Benennung der Stadt.
Den Anlass zur Gründung Montreals im Jahre 1642 gaben strategische Überlegungen der französischen Krone. Samuel de Champlain, der erste Generalgouverneur Neufrankreichs, hatte erkannt, dass man neben den beiden Handelsposten Tadoussac und Québec einen weiteren, mehr im Landesinneren gelegenen strategischen Knotenpunkt benötigte. Ziel war zum einen, einen besser gelegenen Umschlagplatz für den wirtschaftlich immer bedeutender werdenden Pelzhandel zu schaffen. Dieser wurde durch Trapper und Händler flussaufwärts bei den Großen Seen getätigt. Bis zu diesem Zeitpunkt waren der Weiterverkauf und die Verschiffung der Pelze nach Europa an der weit entfernten Mündung des Sankt Lorenz in den Atlantik abgewickelt worden. Dies war eine Situation, die eine bessere wirtschaftlichen Entwicklung behinderte. Zum anderen sollte die neue Siedlung als Basis für die Erforschung und Inbesitznahme der noch unbekannten landeinwärts gelegenen Gebiete dienen.
Als Champlain 70 Jahre nach Cartier per Schiff erneut die ehemals indianisch besiedelte Insel im Sankt-Lorenz-Strom erreichte, fand er das Dorf der Ureinwohner verlassen.
Die neue Siedlung wurde schließlich am 17. Mai 1642 unter der Führung von Paul Chomedey, Sieur de Maisonneuve gegründet. Der zu diesem Zeitpunkt mächtige Bischof von Québec hatte darauf gedrängt, man möge mit der Neugründung ein streng nach katholisch-religiösen Grundsätzen gestaltetes Siedlungsprojekt ins Leben rufen. Die Kolonie erhielt den Namen Ville-Marie.
In der Folgezeit und bis zum Frieden von Montréal 1701 wurde die Siedlung Opfer zahlreicher irokesischer Angriffe und stand mehrmals kurz vor ihrer völligen Zerstörung.