Before you can defeat Hades, you must go to Phrygia to get an item.

Leave Crete

To get to Phrygia after defeating the Minotaur in Crete and getting the third Token of Love, leave the room where you met the Nymph, then go to the left in the room where you fought the Minotaur, and go through the leftmost door. Then, in the pink area, you can go to the left and enter the door there to find a fountain. Then go to the left from that door and enter the door there. In the red area, go to the leftmost side and enter that door. In the pink area, go to the right and enter that door. In the purple area, go to the left and enter that door. In the pink area, go to the leftmost side and enter that door. In the green area, go to the leftmost side and enter that door. You will find a path to the outside.

Defeat Talos the knight. This is not the same area where you first arrived in Crete, but it looks almost the same (the other side has a blue sky, while the sky here is pink). Go to the left until you reach the sea. Use the Ocarina to call a dolphin, then go to the left along the sea. Ignore the island with the door on it. It leads to Tartarus, but you need to go to Phrygia first.

Go to Phrygia

Continue going left and you will reach Argolis. Go to the left and enter the second door to find Hermes's temple. Talk to him to get a password. Then leave his temple and go to the left to reach the next area. You can fall into the first pit here to reach a snake pit (not a salamander pit) that has a fountain in the middle room. If you go into that pit, the door on the right takes you out of the cave.

If you decided not to use the fountain, then just continue going left until you reach a dead end, and go through the door there. You will be outside of the cave.

Use the Harp at the Sun Monument. Pegasus will take you to Athens. Go to the right if you want a password from Athena. Then go to the left until you reach a dead end. Go through the door, and go through the cave. From here, go to the left until you can go down the stairs. After going down, go to the left to reach the area where you fought Lamia. Go to the sea and play the Ocarina to summon a dolphin. Go left and you will arrive in Phrygia.

Get Past Dark Pegasus

Go to the right and hop off the dolphin. Dark Pegasus will attack. You don't need to battle it. You can just run past it and go into the door on the right. If you want to battle Dark Pegasus, you can hit it with beams from the Divine Sword. It will spit flames as it flies around in loops. Its head is its only vulnerable point, so be sure to aim for it.

After you get past the Dark Pegasus, go into the door to the right of where you encountered it.

Kill Giant Snake #1

There will be Gargoyles floating around this area. Kill them or avoid them. Then go to the rightmost side and enter the door there. From there, go right, killing the salamander, and be sure to kill the other salamander that falls down from above. Then go to the right and you will find a Giant Snake. Stand still to block its fireballs, then jump and shoot beams from the Divine Sword at its head.

Kill Giant Snake #2

After it dies, go up the stairs to the right, and go into the door at the end. From there, go up the nearby stairs. Then kill all the gargoyles so they don't knock you into the pit, then go to the left until you find more stairs, and go up those. Ignore the door, and continue going up stairs until there are no more stairs. Go into the door at the top and you find another Giant Snake.

Get an Ambrosia

After you kill the second Giant Snake, go down the stairs behind where it was. Ignore the door and go to the right, and go down the stairs there. Jump to the left and go into the door, then go to the left and go up the stairs. Go up to the top, then make your way to the right, and go down the stairs at the end to reach the previous area. Go through the door, then go up the stairs until you find another door. Go in to get a final Ambrosia.

Kill Giant Snake #3

Now go down all the stairs until you reach another Giant Snake. Kill it, then keep going down all the stairs until there are no more stairs. Jump all the way to the left and go through the upper-left door of the area. From here, go up all the stairs until there are no more stairs. Go into the door to reach Artemis's Temple. Talk to Artemis to get the Moon Crystal. Talk to her again to get a password.

Now you have everything you need to defeat Hades, so your next destination is Tartarus.