Les Premières Nations Mi'kmaq nommaient poétiquement l'archipel « Menagoesenog », ce qui signifie « îles balayées par la vague ». Bien avant la venue des Européens, ils le parcouraient en quête de poissons, de phoques et de vaches marines. Le 25 juin 1534, Jacques Cartier, dans son journal de bord, baptise à son tour les Îles « les Araynes », du latin arena, c'est-à-dire sable. Il aborde d'abord les Rochers-aux-Oiseaux, qu'il nomme alors « Isle Margaulz » à cause des nombreux volatiles qui s'y trouvent, et ensuite l'Île Brion.
C'est en 1629 que Samuel de Champlain inscrit sur une carte « La Magdeleine » à l'endroit de l'île du Havre-Aubert. On dit aussi que le nom des Îles de la Madeleine n'aurait peut-être été attribué à l'archipel qu'en 1663 par François Doublet de Honfleur, concessionnaire des Îles, en l'honneur de son épouse Madeleine Fontaine.
En 1755, le destin des Acadiens prend une tournure tragique. C'est le « Grand Dérangement ».
Quelques individus échappent à cette déportation et débarquent aux Îles de la Madeleine sous la rude tutelle du marchand Richard Gridley. Ils chasseront le morse et exploiteront les pêcheries des Îles pour ce dernier.
En 1789, suite à la Révolution française, d'autres familles acadiennes originaires de Saint-Pierre et Miquelon se joignent à eux sous la gouverne de l'abbé Jean-Baptiste Allain à qui l'on doit le premier registre conservé. C'est à ce moment-là que commence la véritable colonisation des Îles de la Madeleine. En 1763, les Îles sont d'abord annexées à Terre-Neuve pour passer, en 1774 grâce à l'Acte de Québec, sous la juridiction du Québec.
En 1798, Isaac Coffin en obtient la concession et oblige les Madelinots à payer des rentes pour occuper les terres qu'ils ont défrichées et occupées depuis plus de 25 ans.Ces misères et injustices auxquelles sont alors soumis les Madelinots expliquent leur émigration vers de nouvelles terres. Ils vont ainsi fonder plusieurs villages de la Côte-Nord, dont Blanc-Sablon (1854), Havre-Saint-Pierre, Natashquan (1855) et Sept-Îles (1872). C'est en 1895 seulement qu'une loi du Québec permettra aux Madelinots de racheter leurs terres. Ils mettront dès lors leurs efforts à surmonter leurs difficultés et à viser l'autosuffisance.
Les Madelinots pêcheurs et navigateurs ont certes connu les joies de la vie maritime, mais ils en ont également connu les difficultés. Au-delà de 400 naufrages ont été rapportés aux Îles de la Madeleine. La plupart du temps, il s'agissait de bateaux étrangers qui naviguaient autour de l'archipel et que la tempête rejetait sur la côte. Il est arrivé à quelques reprises que les naufragés choisissent de refaire leur vie dans l'archipel.
Au fil du temps, l'amélioration des moyens de communication a largement atténué l'isolement des insulaires qui conservent une façon de vivre unique. En 2013, la population totalisait 12 721 habitants, dont 5 % environ sont des anglophones majoritairement d'origine écossaise.