Die Ursprünge von Fehmarn liegen in der letzten Eiszeit, als die heutige Insel als Grundmoräne aufgeschüttet wurde. Um etwa 2.000 v. Chr. entstand der Fehmarnsund, womit Fehmarn vom Festland getrennt und zur Insel wurde. Die ersten Bewohner waren Germanen, die Sweber. Um 400 n. Chr., während der Völkerwanderung, wurde Fehmarn durch Slawen besiedelt.

1075 erwähnte Adam von Bremen erstmals die Insel Fehmarn. Im 12. Jahrhundert wurde Fehmarn christianisiert und mit deutschen Bauern besiedelt.
Nach der Christianisierung wurden Kirchen errichtet. In Burg die St. Nikolai-Kirche, in Landkirchen die St.-Petri-Kirche, in Petersdorf die St.-Johannis-Kirche und in Bannesdorf die St.-Johannis-Kirche.
1420 wurde Fehmarn durch den dänischen König Erich von Pommern verwüstet.
Im 15. Jahrhundert ist Burg Glambeck zeitweise durch die Vitalienbrüder besetzt.
Am 3. Mai 1580 wurde die goldene Krone im blauen Meer zur Lehnsfahne der Insel Fehmarn.

Im Jahre 1644 musste sich Fehmarn im Rahmen des dänisch-schwedischen Krieges gegen die Feinde verteidigen, was viele Opfer gab und zu Armut führte.
1669 (Krieg zwischen Dänemark und Schweden) und 1713 (Nordischer Krieg) wurden hohe Kriegssteuern fällig. Nach Kriegen 1848 und 1864 kam Fehmarn zu Preußen, 1871 ins Deutsche Reich.
1872 wütete eine schlimme Sturmflut besonders an der Westküste der Insel.
In beiden Weltkriegen gab es viele Opfer.
1963 wurde die Fehmarnsund-Brücke fertiggestellt.