Критика откликнулась на рассказ еще до того, как было закончено печатание его в «Новом слове». В статье «Литературные очерки» рецензент, выступивший под псевдонимом «Старый писатель», отмечал силу и свежесть таланта Горького. Вместе с тем он утверждал: «Глубокие душевные повороты в непосредственных людях из народа, как известно, происходят и происходили совершенно на иной почве и под давлением и влиянием совершенно иных и не столь мимолетных психических стимулов» («Одесские новости», 1896, № 3697, 22 июля). Автор рецензии упрекал писателя в «излишнем и крайнем реализме», но выражал надежду, что «талантливый автор „Челкаша“, вероятно, в будущем легко сумеет справиться с этими недостатками».
Рецензия эта не удовлетворила молодого писателя. В письме Е. П. Волжиной от 25 июля 1896 г. он писал: «Читал сегодня в газетах отзывы о „Тоске“. Лестно, но всё не то, чего мне нужно. Я могу написать такие вещи, которые поразят, измучают душу читателя. Но пока я не могу серьезно работать — нет времени на это <…> Это горько, Катя, горько и тяжело» (
Вскоре о «Тоске» заговорили и в центральной прессе. Автор анонимного отзыва «Журнальные новости» («Русские ведомости», 1896, № 217, 8 августа) утверждал, что рассказ «Тоска» «имеет интерес только в последней части, где изображается состязание певцов в дрянненьком трактире». Он сравнил эту часть с «Певцами» Тургенева (аналогия, впоследствии фигурировавшая во многих рецензиях).
Наиболее обстоятельный отзыв о рассказе дал В. А. Поссе. Высоко оценивая художественный талант Горького, Поссе в статье «Журнальное обозрение» писал, что «„Челкаш“ и „Тоска“, подобно произведениям наших лучших писателей: Тургенева, Толстого и др.,
Через дна года, после выхода «Очерков и рассказов», Поссе снова обратился к творчеству Горького, в том числе и к анализу «Тоски», в статье «Певец протестующей тоски». Ставя произведения Горького в связь с творчеством Гоголя, Тургенева, Щедрина, Л. Н. Толстого, он сопоставлял «Тоску» с повестью Толстого «Смерть Ивана Ильича». Тоска мельника, в которой «страх смерти смешивается с недовольством, вытекающим из внезапного сознания полной пустоты прожитой жизни», по мнению Поссе, «это — та тоска, которая гложет перед смертью толстовского Ивана Ильича» («Образование», 1898, № 11, стр. 50–51). «Иван Ильич — высокопоставленный и образованный чиновник, Тихон Павлович — полуграмотный мельник, но тем не менее основа их тоски, их ноющего и гложущего душу недовольства жизнью — одна и та же. Приближаясь к смерти, они оба тоскуют, что всю жизнь угнетали живую душу мелкими, мертвыми делами» (там же, стр. 51).
Многие критики восприняли «Тоску» в духе той народнической беллетристики, которая рисовала пробуждение в душе кулака «искры божией». Но рассказ не укладывался в этот готовый трафарет. Беседуя с учителем, мельник не проникся желанным и традиционным для народнической беллетристики «просвещением», сердце его не смягчилось; «покаянный прилив» вылился в бесшабашную попойку. Это вызывало недоумение и ставило в тупик некоторых критиков. А. Басаргин (А. И. Введенский) в статье «Тоскующий талант» писал: «Началось всё как будто ладно, по-должному. Беззаконная купеческая душа ощутила духовный глад, укоры совести и затосковала. А кончилось… кончилось, как часто кончается <…> У Тихона Павловича тоска временная, налетная: тронули — он поднялся из грязи, увидел, что в грязи запачкан, и закручинился, затосковал, а потом опять шлепнулся в грязь и тоска прошла» («Московские ведомости», 1898, № 279, 10 октября). Откровенно выразил свое недовольство концом рассказа критик М. К-ский («Сын отечества», 1896, № 211, 7 августа).