Mesto naj bi ustanovili že Galci v 1. st. p.n.š. Cvetelo je pod Rimljani, ob koncu 4. st. je na kraju stala pomembna utrdba. Ko se je v 5. in 6. st. Bretanija odcepila od imperija, se je iz Anglije v mesto priselilo veliko število keltskih Britov. Poslej je St-Malo stalno ubiral poti samostojnosti in če se je le dalo, ni pripadal ne Bretaniji, ne Franciji, ne Angliji. V njem so se zbirali lastniki ladij, ki so kot zasebniki imeli pravice pleniti po svetovnih morjih. Pojma "corsair" in "privateer" se prav dosti ne razlikujeta od pojma "pirat". V mestu so se stekali zakladi z vsega sveta in v času največje moči so St-Maloju prehod po Angleškem kanalu morale plačevati celo angleške ladje. Številni svetovni raziskovalci so bili iz St-Maloja. Leta 1758 so Angleži mesto neuspešno poskušali osvojiti. Med zavezniško ofenzivo v II. svetovni vojni pa je bilo mesto v obstreljevanju Američanov in Britancev skoraj povsem porušeno (zavezniki so napačno ocenili moč nacistične posadke v St-Maloju). Obnovljeno je bilo šele v letih 1948-60.