Earlier names of the island are Femera, Fimbria, Cimbria parva, and Imbra. As a part of Wagria it was settled by the Slavic Lechitic tribe of Wagri in the Early Middle Ages; the name derives from Old Slavic fe more (in the sea), modern v more. After their conquest and Christianization, they were progressively Germanized.
From the Middle Ages till 1864 Fehmarn formed part of the Danish Duchy of Schleswig. When the duchy was partitioned in 1544, it formed part of the duchy of John the Elder. Upon his death without heirs in 1580, Fehmarn became part of the Duchy of Schleswig-Holstein-Gottorp. After the Great Northern War Fehmarn along with the rest of Schleswig was united with the Danish crown. In 1864 Schleswig passed to Prussia as a result of the Second Schleswig War.
On 26 July 1932, the German Navy's training ship Niobe sank off the island during a sudden squall, with the loss of 69 lives. At Gammendorfer Strand on Fehmarn, within view of the site of the sinking, the Niobe-Denkmal monument was erected.
Since 1963, Fehmarn has been connected to the German mainland by a road and rail bridge crossing the Fehmarn Sound Bridge. It is 963.40 m (3160.76 ft.) long and 69 m high.