Стихотворение первоначально входило в рассказ "О маленькой фее и молодом чабане (Валашская сказка)". В начале 900-х годов М. Горький коренным образом переработал стихотворение, заново написал последнюю строфу, сделал стихотворение самостоятельным произведением и разрешил композитору А. Спендиарову положить его на музыку. В 1903 году появилось первое издание нового текста при нотах. В последующие годы стихотворение неоднократно переиздавалось под заглавиями: "Валашская сказка", "Фея", "Рыбак и фея" и др.
В 1906 году стихотворение вошло в книгу "М. Горький. Песня о Соколе. Песня о Буревестнике. Легенда о Марко", СПБ, 1906. Это -- первая книга из обширной "Дешёвой библиотеки товарищества "Знание", изданной в 1906 году и включавшей более тридцати произведений М. Горького.
В собрания сочинений "Легенда о Марко" не включалась.
Печатается по рукописи, хранящейся в Архиве А. М. Горького.