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