Археологические находки доказывают, что различные племена индейцев проживали на острове Монреаль уже 4000 лет назад. К 1000 году н. э. они начали возделывать кукурузу. За несколько столетий индейцы построили несколько укреплённых деревень. Лаврентийские ирокезы, жившие обособленно от остальных ирокезов, населявших территорию современного штата Нью-Йорк, основали деревню Ошелага у подножия горы Мон-Руаяль за два столетия до прибытия французов. Археологами обнаружены артефакты их жилищ в этом и других местах долины, датируемые по меньшей мере XIV веком. Французский первооткрыватель Жак Картье, посетивший деревню 2 октября 1535 года, оценил население Ошелаги как «превышающее тысячу человек».
Семьдесят лет спустя, французский исследователь Самюэль де Шамплен сообщил, что лаврентийские ирокезы и их поселения исчезли из долины реки Святого Лаврентия, возможно из-за эмиграции, эпидемии европейских болезней, или межплеменных войн. В 1611 году Шамплейн учредил пост для торговли пушниной на острове Монреаль, на месте, которое первоначально называлось La Place Royale, на месте слияния Петит Ривьер и реки Святого Лаврентия.
В 1639 году, Жером Ле Ройер де Ла Доверсер получил титул сеньора острова Монреаль и главы общества «Нотр-Дам де Монреаль», созданного Католической церковью для распространения христианства среди местных жителей. Пол Шомеди де Мезоннёв был в то время губернатором колонии. Так 17 мая 1642 года евангелисты основали миссию-форт на месте сегодняшнего центра города, названную Вилль-Мари (фр. Ville-Marie) в честь Пресвятой Богородицы Девы Марии. Это число считается официальной датой основания Монреаля и в современности отмечается в купе с Днём Виктории в третий понедельник мая.
Вилль-Мари стал центром торговли пушниной и базой для дальнейшей французской экспансии в Северной Америке. К началу XVIII века здесь начинает миссионерскую деятельность католическое общество Святого Сульпиция. Чтобы поддержать французских колонистов они убеждают могавков оставить Вилль-Мари и основать новое поселение в своих бывших охотничьих владениях к северу от реки Оттава.
Канадская территория оставалась французской колонией до 1760 года, когда территории были переданы Великобритании после победы в Семилетней войне. Монреаль был зарегистрирован как город в 1832 году. Открытие канала Лашин позволило судам идти в обход несудоходных Лашинских порогов, а строительство моста Виктория сделало из Монреаля важный железнодорожный узел. К 1860 году Монреаль стал крупнейшим городом в Британской Северной Америке и бесспорным экономическим и культурным центром Канады.
Монреаль был столицей Канады с 10 мая 1844 года (после перенесения столицы из Кингстона) по 1849 год, но потерял свой статус, когда толпа тори сожгла здание парламента в знак протеста против принятия закона о возмещении убытков восстания в Нижней Канаде. По стратегическим соображениям Оттава, расположенная в более удалённом районе страны, была выбрана в качестве столицы. После Первой мировой войны, вследствие принятия сухого закона в Соединённых Штатах, Монреаль стал убежищем для ищущих возможности выпить американцев. В то же время, в городе остро стояла проблема безработицы, которая усугубилась с обвалом фондового рынка в 1929 году и наступлением Великой депрессии.
Во время Второй мировой войны, мэр Монреаля Камийен Уд протестовал против призыва в армию. 2 августа 1940 года он разместил в печати заявление с призывом к горожанам не регистрироваться в федеральном реестре всех мужчин и женщин. Спустя 2 дня Камийен Уд был арестован и без суда и следствия отправлен в трудовой лагерь для интернированных, где находился до 1944 года.
К 1951 году население Монреаля превысило один миллион человек. В 1959 году был открыт Морской путь Святого Лаврентия, позволяющий океанским судам проходить из Атлантики до Великих озёр минуя Монреаль. Это со временем приведет к концу экономического доминирования города. Однако, в 1960-е в Монреале продолжается экономический рост: проводится всемирная выставка Экспо-67, возводятся самые высокие в Канаде небоскрёбы, прокладываются скоростные дороги и строится Монреальское метро.
В 1970-е годы начался период широкомасштабных социальных и политических изменений. Основной их причиной стало стремление франкоязычного большинства сохранить свою культуру и язык на фоне традиционного преобладания англо-канадского меньшинства в сфере бизнеса. Октябрьский кризис и выборы 1976 года, в результате которых у власти оказывается Квебекская партия, провозгласившая своей главной задачей борьбу за государственный суверенитет Квебека, приводят к тому что из города начинается отток англо-канадского капитала и населения. В 1976 году в Монреале проводятся Летние Олимпийские игры. В 1980-х и начале 1990-х годов Монреаль испытывает замедление темпов экономического роста по сравнению с другими крупными городами Канады.
1 января 2002 года, в результате присоединения 27 окружающих муниципалитетов, был образован единый город Монреаль, покрывающий всю территорию одноименного острова. Это вызвало волну возмущения у жителей ряда англоговорящих пригородов. По итогам независимых референдумов, проведенных среди жителей этих пригородов, в июне 2004 года, часть муниципалитетов (13 % населения острова) приняла решение выйти из состава единого Монреаля. В результате отделения, состоявшегося 1 января 2006 года, на острове остались 15 муниципалитетов, включая Монреаль. Тем не менее, отделившиеся муниципалитеты остались связаны с Монреалем посредством совета, занимающегося сбором налогов для оплаты услуг многочисленных служб.