Неподалеку от Иолка, на берегу полуострова Магнезия, начали строить корабль. Руководил строительством знаменитый корабельный мастер Apг. Корабль получился так хорош, что многие говорили, будто его помогала строить сама Афина. Кораблю дали имя «Арго», что значит «быстрый», а герои, собравшиеся на нем плыть, назвали себя аргонавтами.
Аргонавты покинули Грецию и пустились в далекий путь. В то время еще не существовало достаточно совершенных навигационных приборов, и даже самые дальние плавания, как правило, совершались вдоль берегов или от острова к острову. Рассказ о плавании «Арго» изобилует названиями географических пунктов, в которых останавливались аргонавты. Первую остановку они сделали на острове Лемнос. Этот остров пользовался у греков дурной славой. Известный греческий историк V века до н. э. Геродот писал, что на Лемносе, вопреки общепринятым законам, власть принадлежала женщинам. (Вероятно, на Лемносе, действительно, дольше, чем в Греции, сохранялись остатки матриархата.) Миф об аргонавтах объясняет это явление следующим образом. Женщины Лемноса не принесли вовремя жертву Афродите, и богиня любви отвратила от них их мужей. Оскорбленные женщины решили, что могут обойтись и без них, поубивали всех мужчин на острове и учредили женское царство.
Тем не менее аргонавтов жительницы Лемноса встретили вполне доброжелательно, и путешественники надолго задержались на острове. Царица Лемноса Гипсипила стала возлюбленной Язона и родила ему двоих сыновей. Многие аргонавты также обзавелись возлюбленными и детьми и были готовы остаться на Лемносе навсегда. Но Геракл стал сурово упрекать товарищей, забывших о цели своего похода, и они, устыдившись, снова пустились в путь.
Миновав Фракийское море, через Гелласпонт аргонавты вышли в Пропонтиду и пристали к берегу, на котором жили долионы — миролюбивый и гостеприимный народ.
Долионам издавна досаждали их соседи — шестирукие великаны. Аргонавты решили помочь долионам, вступили в бой с великанами и уничтожили их. Благодарные долионы и их царь, юный Кизик, поклялись аргонавтам в вечной дружбе.
Аргонавты отправились дальше. Вскоре поднялась буря. Целый день «Арго» носился по волнам, а ночью его прибило снова к земле долионов. Не узнав в темноте друзей, долионы приняли их за морских разбойников и встретили с оружием в руках. Произошла короткая схватка, в которой Язон убил долионского царя.
Когда взошло солнце, аргонавты и долионы увидели свою роковую ошибку. Три дня и три ночи оплакивали они убитых, а вместе с ними плакали нимфы окрестных лесов, рек и гор.
Затем «Арго» продолжил свой путь.
Много приключений пришлось пережить аргонавтам, прежде чем они достигли Колхиды.