Впервые напечатано в «Самарской газете», 1895, номер 98, 11 мая; номер 100, 14 мая; номер 105, 20 мая; номер 106, 21 мая; номер 107, 24 мая, с подзаголовком «Валашская сказка». В воспоминаниях «В.Г.Короленко» Горький говорит о том, что сказка была написана ещё в Тифлисе, то есть в 1892 году. Одна из песенок чабана, начинающаяся словами «В лесу над рекой жила фея», неоднократно переиздавалась под названиями: «Легенда о Марко», «Валашская сказка», «Валашская легенда», «Фея», «Рыбак и фея». Текст этой песни после первой публикации был значительно исправлен стилистически, изменена концовка стихотворения и прибавлено заключительное четверостишие. В собрания сочинений сказка не включалась. Печатается по тексту «Самарской газеты».