В октябре 1879 года «в отвращение влияния его самостоятельных и дерзких наклонностей на других политических ссыльных, имеющих молодые лета», как писал глазовский исправник в докладе по начальству, Короленко вновь был выслан, теперь в наиболее отдаленный район Глазовского уезда — Березовские Починки. «Это ни село, ни деревня даже, — писал Короленко, — это просто несколько дворов, рассеянных на расстоянии 15–20 верст среди лесной и болотистой местности». В Березовских Починках проявилась одна из самых характерных черт Короленко: его глубокая близость к народу. В письмах из Березовских Починок он неоднократно пишет о стремлении быть полезным людям, среди которых он живет, и когда он писал родным: «Начинаю карьеру сапожника» — в этом не было ни рисовки, ни забавы, ни какого–либо позерства. В этом занятии Короленко видел живую необходимость. Он стремился к тому, чтобы на него не смотрели как на барина, и в одном из своих писем с большим удовлетворением рассказывает о том, что березовские крестьяне относятся к нему с уважением и называют его «мужиком роботным». В то же время работа сапожника давала ему возможность непосредственного общения с крестьянами. В письмах он настойчиво просит прислать ему сказку Щедрина «Как один мужик двух генералов прокормил», видимо желая использовать ее в пропагандистских целях. «Я здесь, к счастью, — пишет Короленко в письме от 11 января 1880 года, — не лишен возможности потолковать по душе с людьми, которым понятны не одни непосредственные брюховые интересы; и здесь выпадают хорошие, чистые минуты, когда забываешь и болота и леса и когда удается потолковать об окружающих, порой невеселых впечатлениях, разобраться в них; а там опять станешь свежее и бодрее смотреть на свет». Здесь Короленко, столкнувшись с жизнью крестьян, смог убедиться в иллюзорности народнических представлений об идеальном устройстве крестьянского быта.
Березовскими Починками не окончились ссыльные скитания молодого писателя. Вятская администрация не оставляла в покое Короленко, видя в нем весьма опасного врага самодержавия. В январе 1880 года против него было затеяно новое дело. Он обвинялся в самовольных отлучках с места ссылки и в недозволенных связях с политическими ссыльными. Вероятней всего, личность Короленко продолжала интересовать и высшие полицейские власти в связи с усилившейся деятельностью народовольцев. Вскоре после покушения на Александра II в январе 1880 года Короленко был арестован, доставлен в Вятку, а затем заключен в вышневолоцкую политическую тюрьму. Предполагалась ссылка его в Восточную Сибирь, но из Томска писатель был возвращен на поселение в Пермскую губернию.
Находясь в Перми на положении ссыльного, Короленко перепробовал несколько профессий: сапожника, табельщика, письмоводителя стола статистики на Уральско–Горнозаводской железной дороге. Здесь он работает до 11 августа 1881 года — дня очередного ареста, после которого последовала самая длительная и самая отдаленная ссылка.
Первого марта 1881 года был убит народовольцами Александр II. Правительство Александра III потребовало, чтобы часть политических ссыльных была приведена к специальной присяге. Текст такой присяги получил и Короленко, но подписать его демонстративно отказался. В заявлении на имя пермского губернатора Короленко называет факты дикого произвола царской власти, действия которой направлены исключительно на подавление народа. Вот почему, пишет Короленко, «совесть запрещает мне произнести требуемое от меня обещание в существующей форме». «Я не мог поступить иначе», — сообщал он тогда же в письме к брату.
В отказе от присяги полицейские власти усмотрели особо «враждебное настроение». В дело «государственного преступника», «сапожника и живописца», как именовался Короленко в жандармских документах, была дополнительно внесена резкая характеристика, требовавшая самых суровых мер наказания. Его арестовали и, соблюдая особые предосторожности, как крайне опасного преступника увезли в Сибирь. Не зная, что его ждет в дальнейшем, доведенный до отчаяния, Короленко, находясь в одиночке военнокаторжного отделения тобольской тюрьмы, написал стихотворение, где выразил невеселые свои настроения:
Пессимистические мотивы стихотворения выражали лишь настроение минуты, ибо никогда больше они не повторялись ни в письмах, ни в творчестве Короленко.
В декабре 1881 года Короленко был доставлен в слободу Амгу Якутской области, расположенную в нескольких сотнях километров от Вилюйска, где в ту пору томился Чернышевский. Здесь в тяжелых условиях, вдали от каких–либо культурных центров началась его работа над такими произведениями, как «Сон Макара», «Убивец», «В дурном обществе». Однако выступать в печати ему было категорически запрещено. «Исправник прямо объявил мне, — писал Короленко в одном из своих писем из Амги, — что писать для печати безусловно не допускается».
Вспоминая о своих ссыльных скитаниях, Короленко иронически писал, что «в народ» он «был доставлен на казенный счет». Жизнь в Амге столкнула его с новыми для него формами народного быта и поставила, как он сам об этом сказал, «в отношения полного равенства» с народом: он шил сапоги, выполняя заказы «на сторону», и пахал землю. В то же время Короленко с глубоким вниманием изучал жизнь якутского народа, записывал фольклор, знакомился с языком. Впечатления тех лет послужили основанием для целого ряда сибирских рассказов и очерков, которые составили значительную часть в творческом наследии писателя. В 1885 году Короленко получил разрешение возвратиться в Европейскую Россию без права жительства в столичных городах. Он поселился в Нижнем Новгороде, где и прожил более десяти лет.
Свое литературное призвание Короленко осознал еще в юношеские годы. Как говорил сам писатель, у него еще «с юности была привычка облекать в слова свои впечатления, подыскивая для них наилучшую форму, не успокаиваясь, пока не находил ее».
Впервые Короленко выступил в печати в 1878 году. Это была газетная статья об уличном происшествии, в котором писатель разглядел проявление полицейского произвола над петербургской беднотой.
В следующем году появились в печати «Эпизоды из жизни искателя», а вскоре «Ненастоящий город» и «Яшка» (1880). Уже в «Ненастоящем городе» Короленко достигает значительного мастерства. В правдивом изображении захолустного города, жизнь которого «бьется в тоске и скудости», а сам он напоминает «амфибию с недоразвившимися задатками», проявилось стремление Короленко к реализму, к глубоко правдивому изображению действительности. Писатель подводил читателя к мысли, что выход из того тоскливого прозябания, в которое была погружена жизнь «ненастоящего города», не в возврате к первобытным формам существования, о чем говорила народническая литература, а в развитии промышленности, в установлении новых отношений между городом и деревней, которые породят новых, настоящих людей и откроют дальнейшую перспективу борьбы за народное счастье.