При спуске на воду на верфи «Германия» в Киле в марте 1921 года получил имя «Магдалена Виннен II» (Magdalene Vinnen II) по имени Магдалины Виннен, жены основателя, владельца судоходной компании, заказчика судна Фридриха Адольфа Виннена (суда компании носили имена членов семьи). В своё время корабль был четвёртым по величине парусником в мире. Первоначально эксплуатировали на южно-американской и австралийской линиях.
В 1936 году был перекуплен компанией «Северо-немецкий Ллойд» и переименован новым хозяином в «Коммодор Йонсен» («Kommodore Johnsen») по имени Николаса Йонсена, легендарного капитан-коммодора компании «Хаппаг-Ллойд», и был переоборудован в учебный парусник.
Во время Второй мировой войны судно находилось в составе вспомогательного флота и использовали для доставки снабжения войскам под буксиром. В соответствии с решением Потсдамской конференции о репарациях Германии странам-победителям, судно передано Союзу ССР в декабре 1945 года и переименовано в «Седов».
Первое плавание с флагом СССР барк совершил в июне 1952 года. В 1956 году прошёл переоборудование. До 1966 года принадлежал Военно-морскому флоту СССР, после — Министерству рыбного хозяйства. Министерство рыбного хозяйства под управлением министра Ишкова планировало утилизировать барк Седов в 1975 году, однако, благодаря Аде Салтыковой (Лазо)[4], Роману Лазаревичу Кармену, Тимуру Гайдару барк Седов был отремонтирован и продолжил службу. С 1975 по 1981 год вместе с капитальным ремонтом прошёл модернизацию. Как вспоминал капитан парусника В. Т. Роев: «От старого судна остались только воспоминания, корпус, рангоут да водонепроницаемые переборки». С 1981 по 1991 год портом приписки была Рига, Латвийское производственное объединение рыбной промышленности («Латрыбпром»). «Седов» служил учебным судном Балтийскому отряду учебных судов ВРПО Запрыба МРХ СССР. Ещё до распада СССР летом-осенью 1991 года переведён в российский порт, так же, как и второй по величине парусник «Крузенштерн». «Седов» был приписан к Мурманскому государственному техническому университету, «Крузенштерн» — к Балтийской государственной академии рыбопромыслового флота (город Калининград).
В 1991 году в парусной регате[5] занял первое место. В 1995 году в ней же снова занял первое место[6].
В 2000 году в связи с долгами российского правительства швейцарская компания Noga добилась ареста «Седова», пришедшего на международное шоу во французский Брест. Однако адвокат Мишель Куимбер, представлявший интересы Мурманского технического университета, на чьём балансе и был «Седов», доказал суду, что правительственной собственностью корабль назвать нельзя. Также арест парусника называли причиной отказа Владимира Путина встретиться с Жаком Шираком во время саммита «Большая семёрка».
В 2010 году барк посетил Голландию, Исландию и другие европейские государства[7].
В 2011 году «Седов» отметил своё 90-летие. В 2012 году «Седов» отправился в своё первое кругосветное плавание продолжительностью более 13 месяцев. 20 июля 2013 года кругосветное плавание завершилось там же, где и началось более года назад, на набережной Лейтенанта Шмидта в Санкт-Петербурге.
В 2015 году парусник совершил экспедицию, посвящённую 70-летию Победы в Великой Отечественной войне, посещая разные порты Европы[8].
В настоящее время принадлежит калининградскому государственному техническому университету. Несмотря на почтенный возраст, по-прежнему участвует в парусных регатах (ростокской и других).