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