Только через продолжительное время режим содержания Дзержинского улучшился. Через брата Станислава он смог получать книги. Начинает Дзержинский и системное изучение немецкого языка. Впрочем, послабления были не во всем — и Дзержинский вынужден был обращаться с заявлением на имя тюремной администрации с протестом против запрещения пользоваться марками, бумагой и конвертами, оставленными для него в тюремной конторе Станиславом. К этому времени вследствие длительного тюремного заключения у него возникли проблемы со здоровьем, особенно ухудшилось зрение: «глаза немного разгулялись», как писал об этом сам Дзержинский.
Постепенно сформировалось обвинение. Дзержинского обвиняли в принадлежности «…к тайному преступному сообществу, именующему себя «Союз борьбы за освобождение рабочего класса». Он подавался, несмотря на свой юный возраст, как уже сформировавшийся революционер, опасный для режима. «Как по своим взглядам, так и по своему поведению и характеру, — писал виленскому прокурору начальник ковенского жандармского управления, — личность в будущем очень опасная». Обвинение в принадлежности к «Союзу борьбы за освобождение рабочего класса» было не случайным. По делу Петербургского союза проходил Борис Гольдман (Горев) (член союза с 1895 г.), с которым у Дзержинского оставались личные связи. Весной 1897 г. Горев был арестован, после чего закономерным было внимание властей к его виленским знакомым. Всего по «делу Дзержинского», как оно теперь именовалось, проходило 12 человек.
12 (24) мая 1898 г. Николай II утвердил высылку Дзержинского под надзор полиции в Вятскую губернию на три года. 10 (22) июня начальник ковенской тюрьмы Набоков объявил об этом решении заключенному.
Впрочем, срок был неокончательный. В 1949 г. в Литве был обнаружен архивный документ царского Министерства юстиции. В нем прокурору виленской судебной палаты сообщалось о новом распоряжении императора, отменяющем первоначальное решение о ссылке на три года и устанавливающем высылку Дзержинского на 5 лет в Восточную Сибирь. Однако это предписание уже запоздало, и Дзержинский без суда в административном порядке был выслан на три года в Вятскую губернию, под надзор полиции. Зато в Восточную Сибирь, по высочайшему повелению, на 4 года были сосланы летом 1898 г. студенты Санкт-Петербургского университета, в т. ч. Борис Гольдман. В. И. Ленин был сослан в Восточную Сибирь еще в 1897 г.
В первую высылку Феликса провожала сестра Альдона, ждавшая ранним утром выхода партии заключенных у ворот тюрьмы. «Они были закованы в кандалы, — вспоминала Альдона, — среди них был и Феликс. Сердце мое сжалось, когда я увидела брата. Я заплакала».
Путь к месту административного наказания продолжался долгих два месяца. Сначала железной дорогой до калужской тюрьмы, а затем от Калуги на переполненных пароходах по Оке. В Нижнем Новгороде Дзержинского вместе со студентом Н. М. Величкиным и другими политическими ссыльными для острастки специально посадили в общую камеру со 120 уголовниками. Несмотря на протесты Дзержинского и его товарищей, практика соединения в камерах политических и уголовных не была прекращена.
«Дорога была чрезвычайно приятная, если считать приятными блох, клопов, вшей и т. д. Я больше сидел в тюрьмах, чем был в дороге. По Оке, Волге, Каме и Вятке я плыл пароходом. Чрезвычайно неудобная эта дорога. Заперли нас в так называемый «трюм», как сельдей в бочке. Недостаток света, воздуха и вентиляции вызывал такую духоту, что, несмотря на наш костюм Адама, мы чувствовали себя как в хорошей бане. Мы имели в достатке также и массу других удовольствий в этом же духе».
27 июля 1898 г. Дзержинского привезли вместе с другими заключенными в Вятку, и в ожидании парохода до Нолинска их отвели в местную тюрьму. Пароход из Вятки в Нолинск сел на мель, поэтому Дзержинский ждал пересылки почти две недели. 6 августа Дзержинский письменно обратился к вятскому губернатору Николаю Михайловичу Клингенбергу (известному по Крожскому инциденту) за разрешением отправиться за собственный счет в Нолинск на частном пароходе, «без конвоя, ибо средств на оплату конвоиров не имею». Заявление Дзержинского заинтересовало губернатора, ранее занимавшего эту должность как раз в «польских территориях», и он назначил встречу.
Встреча с губернатором Клинбергером литературно описана в книге Романа Гуля, где ей уделена отдельная 6-я глава.
«Чиновнику особых поручений князю Гагарину губернатор Клингенберг приказал привезти к нему написавшего письмо Дзержинского.
— Кто он, собственно, такой? — не без брезгливости спрашивал губернатор.
— Неокончивший гимназист… дворянин… совсем юный…
Губернатор захохотал: «Уди-ви-тель-ны-е времена! Неокончившие гимназисты занимаются рабочими вопросами! А ну, пришлите-ка его ко мне, я его отчитаю. Тюрьма, наверное, дурь-то из него выбила!».
И через час в дверях губернаторского кабинета появился высокий, бедновато одетый молодой человек, с бросающимся в глаза бледным энергичным лицом и блуждающей на тонких губах усмешкой. Губернатор с любопытством оглядел вошедшую фигуру.
— Ссыльный Феликс Дзержинский, — проговорил вошедший звенящим польским акцентом.
— Так вот какие у нас революционеры! Недоучившиеся гимназисты! — гаркнул по-военному губернатор, стукнув кулаком по столу, и побагровел.
— Посмотритесь в зеркало, молодой человек! У вас молоко на губах не обсохло, а туда же, сунулись «рабочими вопросами» заниматься! Что вы смыслите?! Надеюсь, тюремное заключение образумило вас! У вас есть мать и отец? Сколько вам было лет, когда вас арестовали?