С осени 1886 г. Водовозов занимался нелегальным изданием в литографированном виде религиозно-философских трактатов Л. Н. Толстого и книг о социализме и истории революционного движения в России, а в феврале 1887 г. был арестован по доносу и после следствия в январе 1888 г. сослан в Архангельскую губернию, в Шенкурск, на 5 лет. В переписке О. Ф. Миллер, которого Водовозов называет своим «учителем, другом и товарищем», старался приободрить юношу: «работайте и не хандрите»16, а мать с В. И. Семевским навестила сына в Шенкурске, куда к нему приезжал и С. Ф. Ольденбург. «В ссылке, — писал Водовозов, — впервые я изучил сочинения Карла Маркса, которые оставили глубочайший след на всем моем мировоззрении. Я не сделался ортодоксальным марксистом, но и перестал быть безусловным последователем Чернышевского, каким был раньше. Всего ближе, пожалуй, мне было учение русского истолкователя марксизма Николая — она [Н. Ф. Даниельсона], но и с ним я был не вполне согласен. Во всяком случае, в области теоретической я с тех пор считал себя критическим марксистом»17.

Благодаря хлопотам матери, которая, обивая пороги высоких кабинетов, умела настоять на своем («особенно боялся ее натиска министр народного просвещения Делянов, да и Дурново в должности директора департамента полиции ей в конце концов уступал»18), Водовозов получил разрешение на временное пребывание в Петербурге с мая по сентябрь 1890 г., а затем срок продлили еще на два месяца, для сдачи экзаменов на степень кандидата прав. В столице Водовозов познакомился с Ольгой Ульяновой, которая писала о нем старшей сестре: «он — очень умный человек, любит говорить и говорит интересно»19. Еще до ареста Водовозов пару раз встречался и с Анной Ульяновой, вышедшей замуж за М. Т. Елизарова, вместе с которым Водовозов учился в университете, а через Ольгу познакомился и с ее старшим братом Владимиром, исключенным из Казанского университета и приехавшим в Петербург, чтобы выяснить порядок сдачи экстерном государственных экзаменов, — и даже провел его на один из них. В январе 1891 г. кандидат прав Водовозов вернулся в Шенкурск, где 15 февраля вступил в брак с освобожденной еще в июле из ссылки 25-летней Верой Петровной Шейдаковой. Дочь бросившего жену и детей саратовского купца 2‐й гильдии, слушательница Высших женских курсов в Москве и участница народнических кружков, она провела 14 месяцев в Саратовском тюремном замке и, сосланная в июле 1887 г. в Архангельскую губернию на 3 года, этапом была отправлена в Холмогоры, а оттуда, в марте 1888 г., — в Шенкурск; в июне стрелялась из‐за несчастной любви, но через два с половиной года, сблизившись с товарищем по ссылке, вышла за него замуж.