The first text Andersen called a "fairy-tale" was "The Diving Bell. A Fairy-tale from the Bottom of the Ocean", which appeared in 1827 in Johan Ludvig Heiberg's literary magazine Kjøbenhavns flyvende Post. However, it is not really a fairy-tale but a fantastic story, a comic fantasy in verse. The text was later incorporated as chapter 12 in his first book, Fodreise (1829).
The first real fairy-tale Andersen published was "Dødningen" (The Dead Man), which concluded his collection of poems from 1830, Digte. It is an old folktale, which is found in many civilizations (e.g. in the Apocrypha of the Old Testament known from "Tobias' Book" or "Tobit's Book"), here retold partly as a local legend and in a witty literary style inspired by the German writer Musäus. It was this tale that Andersen completely rewrote in 1835 as far as style and narrative technique are concerned, giving it the title "The Travelling Companion".
In 1835 appeared the two first booklets which he called Fairy-tales told to the children, (Eventyr, fortalte for Børn) a title he kept up to and including 1841. In 1843 he changed it to Nye Eventyr - New fairy-tales. In 1852 he introduced the title Stories (Historier) signalling a new realism, and later he mixed these two designations, fairy-tales and stories. See the index of fairy tale collections.