В конце июня Седов венчался с Верой Валерьяновной. В тот же день молодые выехали в Архангельск. В этом же поезде в третьем классе ехали семеро спутников-рабочих, а в багажном вагоне были ящики с инструментами для наблюдений и съемок, ящики с консервами и палатки.
Свадебное путешествие было переполнено хлопотами о снаряжении гидрографической экспедиции. За пять дней в Архангельске нужно было закупить провизию, строительные материалы, карбасы и теплую одежду, а также подыскать недостающих трех человек в команду. Кроме того, у астрономического столба на стенке дирекции порта Седов несколько раз определял время, чтобы привести в порядок свои хронометры и на местной метеорологической станции выводил поправки анероидов.
В полночь 21 июля пароход «Великая княгиня Ольга Константиновна» отплыл из Архангельска с участниками экспедиции на борту. Через три дня «Ольга» вошла в губу Крестовую на северном острове Новой Земли и бросила здесь якорь. Неприветливо встретила Новая Земля исследователей. Два дня дул десятибальный «сток» ветер с востока. Выгружаться на берег нельзя было. Седов записал в свою тетрадь, как выглядит губа Крестовая. Это описание сделано сжатым языком навигатора и составителя карт – оно точно, полно и в нем нет ничего лишнего. Стачала о том, что при подходе с моря к губе Крестовой открываются на заднем плане губы остроконечные вершины, покрытые вечным снегом и тесно друг к другу прилегающие, В ясную погоду они видны за пятьдесят с лишним миль. По мере приближения судна к берегу все более вырисовывается обрыв Таран, удивительно похожий на форштевень броненосца, – он обращен на северо-восток. «Южный берег губы, – писал Седов, – представляет собой возвышенную холмистую поверхность, спускающуюся отлогими уклонами к морю… Берег изрезан оврагами, по которым стекают в губу ручьи и падают водопады.
Северный берег так же скалист и утесист, но несколько ниже южного… Оба берега усеяны подводными и надводными камнями.
Восточная половина губы окружена со всех сторон цепью высоких остроконечных гор, покрытых вечным снегом и ледниками…» >{10}
Еще в 1902 году на «Пахтусове» Седов ходил вдоль новоземельских берегов, производя съемку и описания.
И в следующее лето он плавал в этих водах и бродил с компасом по этим берегам. Война с Японией прекратила его участие в многолетней экспедиции для съемки берегов Ледовитого океана, предпринятой Главным гидрографическим управлением с целью подготовить навигацию Северным морским путем.
В 1904 году он, по добровольному желанию, был отправлен на Дальний Восток. Его назначили в Амурскую речную флотилию