Здание, которое сегодня носит название «Североход», появилось в Ярославле еще в 1874 году. Тогда на улице Романовской (сегодня — улице Победы) выросло промышленное здание, где расположилась табачная фабрика Вахрамеевых «Феникс», на которой производили махорку. Предприятие стремительно развивалось и к началу XX века стало крупнейшим в губернии, а его продукция была популярна по всей России. Но во время подавления «белогвардейского мятежа» здания фабрики очень пострадали и опустели на долгое время.

Новую жизнь в это место вдохнула обувная фабрика «Североход», возникшая в марте 1924 года. Рабочие В. П. Теляков, А. А. Беляков, А. А. Смирнов, В. Ф. Серов, И. Ф. Телюшкин и другие их единомышленники собрались в производственный коллектив при Ярославской бирже труда, арендовали инвентарь и организовали обувную мастерскую. Но производство росло большими темпами, и уже через 4 года им потребовалось более крупное помещение, чем то, которым они располагали. Тогда они вспомнили про пустующее здание на улице Победы и обратились к вышестоящим организациям с просьбой оборудовать его под обувную фабрику. Просьба была выполнена, и работа закипела: в 1940 году было выпущено 1397 тысячи пар обуви, что в 64 раза больше, чем в 1927 году. А в военное время фабрика работала на нужды армии: изготавливала обувь и брезентовые палатки для госпиталей.

Годы шли, обувь «Северохода» имела очень хорошую репутацию среди покупателей, фабрика расцветала и развивалась: приходили новые сотрудники, открывались новые цехи, появлялось новое оборудование. Но в 60-е годы, в связи с появлением в СССР зарубежной обуви, продукция «Северохода» ушла на второй план. Ярославская обувь, конечно, отличалась качеством, но во внешнем виде очень уступала румынским и чешским моделям.

В начале 90-х фабрика была акционирована. Всё это привело к тому, что одна ярославская компания в 2001 году выкупила крупный пакет акции «Северохода». Руководство фабрики привлекло к разрешению ситуации бизнесмена Сергея Валдаева, в чьих руках в итоге оказался котрольный пакет акций «Северохода». Компания тоже сдалась и продала Валдаеву ранее выкупленный пакет акций. И в 2002 году предприятие выкупило землю, которое находилось под его зданиями. Производство постепенно перемещалось в другие здания на Тормозном шоссе, а корпуса на улицах Некрасова и Победы стали сдаваться под офисы и магазины. Тогда, в 2002 году, и был открыт вещевой рынок «Североход».