Возник в начале VI века, когда бритты под давлением англов и саксов стали переселяться на южный берег Ла-Манша. Впервые упоминается как местожительство кельтских монахов Аарона Алетского и Брендана. Своё наименование получил в честь святого Мало.

В раннем средневековье на месте Сен-Мало было предместье города Алет (фр.), служившего местопребыванием епископа на земле кориосолитов. Городом Сен-Мало стал после того, как в середине XII века епископ Жан из Шатильона перенёс сюда из Алета епископскую кафедру. За обладание крепостью на острове в устье реки в XIV—XV веках долго спорили герцоги Бретани и короли Франции.

Золотой век Сен-Мало пришёлся на XVI век, когда он стал гнездовьем прибрежных каперов и добился значительной степени автономии от королевских наместников. Во время смуты 1590—1594 годов жители Сен-Мало изгнали королевского наместника и объявили город самостоятельной республикой. Время городской вольницы изображено в опере Цезаря Кюи «Флибустьер» («У моря»).

В XVII веке Сен-Мало продолжал оставаться западной столицей французских каперов (Дюге-Труэн, Сюркуф и др.)[1]. Грандиозные городские укрепления создавались по проектам знаменитого инженера-фортификатора Вобана. Основание в Бретани порта Лорьян для торговли с заморскими колониями подорвало значение Сан-Мало как основной гавани Бретани. К концу XVIII века эпоха процветания была для Сен-Мало в прошлом.

При высадке союзников в 1944 году на территорию материковой Европы старый город был практически стёрт с лица земли. То, что сегодня видят туристы, было воссоздано в 1948—1960 годах.

В 1967 году в заливе Сен-Мало построена приливная электростанция Ля-Ранс[2], так как здесь отмечены самые сильные приливы в Европе.

Современную известность городу принёс саммит Тони Блэра и Жака Ширака в 1998 году, когда они обсуждали некоторые вопросы европейской безопасности.[3]