Еще два судна – «Андромеда» и «Печора» – были зафрахтованы у российских судовладельцев. На все суда Морское министерство направило своих представителей, имевших опыт полярных плаваний.
Начало экспедиции было встречено российской общественностью восторженно, а ход ее широко освещался прессой.
По сути, спасательная экспедиция была разделена на две отдельные части. На поиски «Святого вмч. Фоки» Г. Я. Седова направлялись три судна. Основным в этой части экспедиции стало парусно-моторное судно «Герта». Его экипаж состоял из 22 человек, в основном архангельских поморов, имевших опыт работы в Арктике, под командованием капитана И. П. Ануфриева.
На борт «Герты» был погружен запас продовольствия и снаряжения из расчета на возможную зимовку, а также на оказание помощи экспедиции Седова в случае ее обнаружения и организации депо (складов) на Новой Земле и Земле Франца-Иосифа. На борту «Герты» находился представитель Морского министерства, начальник этой части экспедиции капитан I ранга Исхак Ибрагимович Ислямов, офицер Российского Императорского флота с многолетним опытом плаваний в качестве командира.
Для раннего, первичного обследования северо-западного побережья Новой Земли и поисков там следов седовской экспедиции предназначалось вспомогательное судно – зверобойная шхуна «Андромеда», командовал которой опытный полярный капитан Г. И. Поспелов. Представителем Морского министерства на шхуну был назначен штурман В. А. Абдрашитов. Уже в середине июня «Андромеда», зимовавшая в селении Шельпино на Мурмане, направилась к берегам Новой Земли для выполнения задания, также имея на борту большой запас продовольствия и снаряжения.
«Герта» в конце июля 1914 года прибыла из Христиании в Александровск, где ее уже ожидал пароход «Печора», доставивший из Архангельска уголь, теплые вещи и оборудование экспедиции. В начале августа экипаж «Герты» получил известие о начале Первой мировой войны. Поскольку селение Александровск было совсем небольшим (в нем проживало менее тысячи человек), капитан Ислямов оказался там старшим военным чином, и ему в этом качестве пришлось принять участие в различных мероприятиях, связанных с обстоятельствами военного времени. Все это задержало выход экспедиции в море на две недели.
К этому времени экипаж «Андромеды», добравшись до Новой Земли и тщательно осмотрев западный берег архипелага от Маточкина Шара до острова Панкратьева, обнаружил место зимовки экспедиции Г. Я. Седова 1912/13 года, а капитану судна удалось найти в гурии записку, сообщающую, что в августе 1913 года «Святой вмч. Фока» направился к Земле Франца-Иосифа. Оттуда экспедиция намеревалась совершить пеший поход к Северному полюсу. Эти сведения по радиотелеграфу с острова Вайгач были переданы в Александровск, на «Герту». Получив это известие, И. И. Ислямов принял решение направить «Герту» не к Новой Земле, как планировалось ранее, а сразу к южной оконечности Земли Франца-Иосифа – мысу Флора.
В Александровске тем временем на борт «Печоры» был погружен в разобранном виде самолет «Морис Фарман». Самолет предназначался для осмотра с воздуха северо-западных берегов Новой Земли от губы Крестовой до острова Панкратьева. Сопровождали самолет летчик Я. И. Нагурский и механик Е. В. Кузнецов.
Начальник экспедиции приказал «Печоре» следовать к губе Крестовой, куда от острова Вайгач должна была прибыть «Андромеда». Экипажам этих судов предписывалось оказывать всяческую помощь в сборке и подготовке полетов самолета, а также организовать продовольственные склады на случай возвращения экспедиции Г. Я. Седова на Новую Землю.
Вследствие тяжелой ледовой обстановки дойти до Земли Франца-Иосифа «Герта» смогла лишь спустя две недели. Здесь в домике, оставленном английской экспедицией Фредерика Джексона, были найдены несколько записок: самого Г. Я. Седова о планах его экспедиции, его заместителя доктора П. Г. Кушакова и штурмана «Святой Анны» В. И. Альбанова о дальнейших событиях. Из них участники спасательной экспедиции узнали о неудавшемся походе к полюсу и смерти Г. Я. Седова и судьбе экспедиции Г. Я. Брусилова. Стало ясно, что «Святой вмч. Фока» отправился в обратный рейс к Большой земле без своего погибшего командира и с двумя оставшимися в живых участниками экспедиции Брусилова на борту.
На мысе Флора капитан I ранга И. И. Ислямов поднял российский флаг в знак присоединения Земли Франца-Иосифа к владениям Российской империи. Этот шаг был глубоко символичен, поскольку архипелаг был открыт австро-венгерской экспедицией под руководством Карла Вейпрехта и Юлиуса Пайера на парусно-паровой шхуне «Адмирал Тегетхоф» в 1873 году, а в 1914 году Австро-Венгерская империя была одним из противников России на полях начавшейся мировой войны.