Миф о Тесее – первый намек на приближающийся закат критского морского владычества. К нему примыкают и другие предания о критских неудачах. Геракл по пути в страну амазонок побеждает на Паросе правящих там сыновей Миноса и забирает двух его внуков взамен двух своих спутников, убитых на этом острове. Примерно тогда же аргонавты, проплывая мимо Крита, уничтожают медного великана Талоса, забрасывавшего камнями всех, кто приближался к острову с враждебными намерениями. Один из малоизвестных вариантов мифа, трактующий сюжет освобождения Афин от власти Миноса, прямо связывал конец критского морского могущества с созданием флота в Афинах. Согласно этой версии, которую Плутарх взял у какого-то более раннего автора, в Афины с Крита бежал на корабле Дедал, и Минос пустился за ним в погоню на больших кораблях. Но буря занесла Миноса в Сицилию, где он и закончил свои дни, а его сын потребовал от афинян выдачи Дедала, грозя умертвить взятых отцом афинских заложников. Правивший тогда Афинами Тесей пошел на хитрость. Вступив в переговоры с новым царем Крита, он построил, между тем, флот и двинул его к берегам острова. Критяне, не подозревавшие о существовании кораблей у соперников, приняли их за дружественный флот и не препятствовали высадке. Заняв гавань, Тесей устремился к критской столице Кноссу и там, у ворот Лабиринта, убил в сражении царя и его телохранителей. Власть перешла в руки Ариадны, и Тесей, заключив с ней мир и вечный союз, освободил находившихся на Крите сограждан.
Согласно общепринятому варианту мифа, в период правления Миноса держава его, несмотря на отдельные неудачи, не утратила своей мощи. Не случайно художник и строитель Дедал, которого насильственно удерживал Минос, не мог покинуть остров, и лишь воздух – единственная неподвластная людям стихия – открыл ему путь к свободе. Это было последнее свидетельство о силе Миноса. А дальше наступает конец могущества Крита. О нем повествует предание о походе Миноса в Сицилию вслед за непокорным художником и его гибели в неприступном Камике, возведенном Дедалом для местного царя Кокала.
Первый дошедший до нас пересказ этой легенды сохранился в труде Геродота в неожиданной связи с Саламинским сражением: афиняне обратились к критянам с призывом к участию в общеэллинской борьбе с персами; те, прежде чем дать ответ, отправили послов в Дельфы, и пифия напомнила жителям острова, что эллины в свое время не помогли отомстить им за смерть их царя Миноса на Сицилии. Приведя ответ оракула, историк комментирует его рассказом о сицилийской истории критского царя. Минос достигает в поисках Дедала Сицилии (носившей тогда еще название Сикания по населявшему ее народу сиканов), а через некоторое время за ним в ту же Сиканию отправляются почти все критяне, кроме полихнитов и пресиев, и осаждают Камик. Не сумев, несмотря на пятилетнюю осаду, взять город, критяне покидают остров. Смерть Миноса, подробности которой Геродот не сообщает, он датирует третьим поколением до Троянской войны. Продолжая рассказ о дальнейшей судьбе попавших на Сицилию критян, историк пишет, что критские корабли были уничтожены бурей и вместо родины уцелевшие участники похода оказались в Южной Италии, где дали начало роду мессапиев.
Фукидид, считавший критскую талассократию Миноса реальным историческим фактом, ничего не сообщает о Миносе в Сикании, как и о Дедале и Кокале. Это не означает, что Фукидид не знал предания. При нем постановка на афинской сцене трагедии Софокла «Камикейцы», вызывавшая самые живые ассоциации с катастрофической неудачей сицилийского похода самих афинян, сделала сюжет популярным. Поэтому игнорирование его афинским историком показывает, что он не считал поход Миноса реальностью.
Другие греческие авторы отнеслись к мифу с большим доверием. О прибытии Дедала к царю сиканов Кокалу рассказывают Филист и Эфор. Гераклид Понтийский в своей «Минойской политии» связывает изменение старого названия сицилийского города Мака на новое – Миноя с тем, что в этом городе высадился Минос и побежденные варвары приняли здесь критские законы. Аристотель, разбирая критское государственное устройство, сообщает о нападении Миноса на Сицилию и о его гибели в Камике. Филостефан, а также Каллимах в «Причинах» повествуют о том, что Дедал, прибыв в Камик, ожидал сына у дочерей Кокала, которые и убили с помощью кипятка явившегося туда в погоне за Дедалом Миноса.