В случае задержки из-за тяжелых ледовых условий Седов рассчитывал на посылку к его экспедиции вспомогательного судна с углем для обеспечения в следующем году дальнейшего плавания судна в высоких широтах. Седов находил, что подобная экспедиция обойдется государству в 70 тысяч рублей. Такие расходы казались минимальными в то время, как многие зарубежные экспедиции к полюсу затрачивали гораздо большие средства.
В марте 1912 года Седов обратился к начальнику Главного гидрографического управления с просьбой предоставить ему отпуск для достижения Северного полюса.
Одновременно он опубликовал в некоторых газетах статьи о предстоящей экспедиции, призывая читателей вносить пожертвования на ее организацию.
Морской министр Григорович создал особую комиссию для рассмотрения предложения Седова, однако комиссия признала, что намечаемая экспедиция носит «несколько непродуманный характер», и в выдаче денег отказала. Седову было пожаловано «высочайшее пособие» в размере 10 тысяч рублей, но денег было недостаточно и пришлось искать частных жертвователей.
О трудностях Седова узнала английская компания, предложившая предоставить ему все необходимое для экспедиции при условии, что сделанные открытия будут принадлежать Англии, но Седов ответил, что честью Родины не торгует, и прекратил всякие контакты с компанией.
С большим трудом ему удалось собрать 108 тысяч рублей, на которые было зафрахтовано старое парусно-зверобойное судно «Святой мученик Фока». Судно находилось в запущенном состоянии, однако времени для его ремонта не оставалось.
Судно могло взять на свой борт около 10 тысяч пудов угля, к сожалению, на этот раз у него было лишь 7 тысяч пудов, что могло хватить лишь на 23–25 ходовых дней. Продукты для экспедиции были закуплены наспех, воспользовавшись спешкой архангельские купцы подсунули Седову недоброкачественную снедь.
Трудности Седова в подготовке экспедиции все более увеличивались. В команде «Святого мученика Фоки» не было профессиональных моряков, в основном в ней преобладали случайные люди, хотя многие из них были энтузиастами своего дела, например, географ В.Ю. Визе и геолог М.А. Павлов.
С большим трудом Седову удалось достать радиотелеграфную аппаратуру и добиться предоставления отпуска радисту, служащему в военно-морском флоте. Однако перед самым отходом судна в дело вмешалось Морское министерство, отказавшееся отпустить радиста в плавание. Вместе с уходом радиста оказалась ненужной аппаратура, которую пришлось выгрузить и оставить на берегу.
По первоначальному замыслу Седова «Святой мученик Фока» должен был отплыть к Земле Франца-Иосифа в июне: шел август, а судно находилось в порту Архангельска. Лишь 14 августа 1912 года Седову удалось выйти в море.
Три дня спустя «Святой мученик Фока» достиг Новой Земли. 30 августа судно попало в сильнейший шторм, характеризующийся Седовым как «страшный». Все дальше «Святого мученика Фоку» отбрасывало в открытое море, судно дало течь, почти было полностью покрыто водой, вода попала в трюм, и «Святой мученик Фока» лежал на боку, черпая носом воду. По словам Седова, обстановка на судне была «адской, хаотической».
Но «Святой мученик Фока» выстоял и дошел до Крестовой губы. Отсюда Седов намеревался направиться на север, чтобы достигнуть Земли Франца-Иосифа, но непроходимые льды преградили путь судну. В течение трех дней Седов пытался пробиться через льды, но сделать этого ему так и не удалось, и он решил повернуть на Новую Землю.
Здесь он намеревался перезимовать у Панкратьевого острова, в заливе, получившем название бухты Фоки.
Во время зимовки Седов производил мензульную съемку Панкратьевого острова и части берегов Новой Земли. Затем он объездил на санях вдоль всего ее побережья, обогнув ее в северной оконечности, и спустился вдоль Карской стороны от мыса Желания к югу на 32 км. Здесь им была произведена компасная съемка берегов в масштабе пяти верст в дюйме и определен ряд астрономических пунктов.
Экспедиция Седова впервые обошла Новую Землю на суше и пересекла ее поперек в самом широком месте.
В ходе зимовки проводились метеорологические и гидрологические наблюдения на специально оборудованной станции, наблюдались приливы и отливы. Эти наблюдения позволили по-новому осветить вопрос о распространении приливных волн у берегов Новой Земли.
В августе 1913 года Седов решил отправить на Большую Землю часть своих людей во главе с капитаном «Святого мученика Фоки» Захаровым. Они должны были дойти на шлюпке до губы Крестовой, куда два раза в лето приходил пассажирский пароход. Вместе с ними Седов переправил отчет о проделанных научных работах, а самое главное, просьбу незамедлительно поставить на Землю Франца-Иосифа уголь и продовольствие.
Тем же месяцем, воспользовавшись взломом льда, «Святой мученик Фока» направился к Земле Франца-Иосифа. Ввиду быстрого расхода на судне угля приходилось экономить топливо и жечь в топках тросы и старые паруса, но Седов неутомимо вел судно к Земле Франца-Иосифа.