Den lille Havfrue blev trykt første gang i EB 3-37, der udkom 7.4.1837.

Hvornår A har faet ideen til eventyret er uvist, men i et brev 12.2.1836 udtaler Henriette Hanck sit håb om, at A vil tage »Luftens Døtre« med, hvis han kommer til Fyn i løbet af sommeren (BHH 124). Det må formodes, at hun dermed hentyder til, hvad der skulle blive til Den lille Havfrue. Første gang A selv nævner eventyret er dog i et brev til ovennævnte 13.5.1836, hvor det hedder, at »»Havets Døttre« skal skrives enten i Tolderlund [: familien Hanck/Iversens landsted] eller paa Lykkesholm, det er snart bestilt« (BHH 140). Det betyder, at eventyret er skrevet omtrent samtidig med KES, som A påbegyndte på Lykkesholm og afleverede til trykning 24.8.1836. Næste gang, eventyret omtales, er først i et brev til Ingemann 11.2.1837, hvor han lover ham sit nyeste hæfte eventyr. Da digterkollegaen havde forholdt sig kritisk til de første eventyr, giver det nye hæfte A anledning til at udtale: »Det nyeste Eventyr: »»Den lille Havfrue« vil De synes om; det er bedre end »Tommelise« og er [...] det eneste af mine Arbeider, som har rørt mig selv, idet jeg skrev det« (BfA I 369). Bortset fra at det er interessant, at A har ændret titlen fra det artsbetegnende til det individualiserede, er Henriette Hancks omtale af eventyret som betitlet Luftens Døtre bemærkelsesværdig, fordi den tyder på, at A allerede da har haft sig eventyrets slutning klar; noget, der har været ham af central betydning, som det fremgår ndf.

Når A i såvel fortalen fra 1837 (I 20) som i Bemærkninger (4) hævder, at Den lille Havfrue er »aldeles egen Opfindelse«, kan det kun være slutningen, han hentyder til. Dette kommer frem i det ovennævnte brev til Ingemann, hvor A sammenligner eventyret med Fr. de la Motte Fouqués Undine og fremhæver, at han har ladet havfruen gå »en naturligere, guddommeligere Vei« end Undine, der kun kan erhverve en udødelig sjæl ved et menneskes kærlighed (BfA I 369). Bortset fra havfruens længsel efter en udødelig sjæl og hendes opløsning i bølgerne har A.s eventyr dog kun få lighedspunkter med Undine.