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