История происхождения Мадленских островов уходит корнями в глубокую древность, когда архипелаг служил сезонным прибежищем для коренных народов. Племена микмаков называли эти земли Menagoesenog, что в переводе означает «острова, омываемые волной». На протяжении тысячелетий этот регион в Канаде использовался ими для охоты на моржей и рыболовства, задолго до того, как на горизонте появились первые европейские паруса.
Официальное европейское открытие состоялось 25 июня 1534 года, когда французский исследователь Жак Картье во время своей первой экспедиции заметил скалистые берега, облепленные стаями птиц. Первоначально он дал архипелагу имя Araynes (от латинского «песок»), пораженный протяженными песчаными дюнами, которые и сегодня являются визитной карточкой островов.
Современное название закрепилось лишь в середине XVII века. В 1663 году французский предприниматель Франсуа Дубле де Онфлер получил концессию на архипелаг и назвал его в честь своей супруги, Мадлен Фонтен. Несмотря на ранние попытки освоения, постоянные поселения здесь возникли значительно позже, когда богатые ресурсами воды залива Святого Лаврентия стали привлекать рыбаков и охотников на постоянной основе.