В первый раз произведение было напечатано в нижегородской газете «Волгарь» в 1894 году, в двадцати пяти номерах: с номера 80, датированного 8 апреля, по номер 152, выпущенный 6 июля. В письме к А.М. Горькому от 7 января 1910 года доктор В.Н. Золотницкий сообщил, что среди нижегородских знакомых Горького возникла идея издания сборника его ранних произведений с благотворительной целью. Золотницкий также упоминал повесть «Горемыка Павел». Он просил разрешения на публикацию и отмечал, что ранние рассказы будут собраны и отправлены Горькому для просмотра. В письме (без даты) с острова Капри Горький ответил, что будет очень признателен, если В.Н. Золотницкий и другие заинтересованные лица помогут собрать его рассказы.
Горький подчеркивал, что более подходящей для этой цели, возможно, окажется повесть «Горемыка Павел», и просил достать комплект «Волгаря» и перепечатать повесть на машинке. Судя по всему, просьба была выполнена — в Архиве А.М. Горького сохранилась машинопись текста рассказа, являющаяся перепечаткой газетной публикации. Текст машинописи содержит авторские правки. На первых четырёх листах исправления весьма значительны, а дальнейший текст до двадцать второго листа включает замену и вычеркивание отдельных слов. Исправленный А.М. Горьким текст можно считать началом второй, незаконченной редакции повести.
В письме от 18 августа 1930 года к директору Литературного музея имени А.М. Горького в Нижнем Новгороде А.И. Елисееву А.М. Горький сообщал, что повесть «Горемыка Павел» перед публикацией в «Волгаре» была испорчена в две руки: редактор «Волгаря» А.А. Дробыш-Дробышевский, человек сухой, самовлюблённый и упрямый, вычеркнул из повести фигуру повара, которая присутствовала в ней с начала до конца, а затем вмешался цензор (письмо опубликовано в «Комсомольской правде», 21 июня 1939 года). Повесть не была включена в собрание сочинений. Поскольку новая редакция повести была лишь начата, в данном издании «Горемыка Павел» публикуется по тексту газеты «Волгарь».