Ο Αλθαιμένης ήταν γιος του Κατρέα, ο οποίος ήταν γιος του Μίνωα και τον διαδέχθηκε στη βασιλεία της Κρήτη. Ο Κατρέας είχε λάβει ένα χρησμό ότι θα σκοτωθεί από το χέρι ενός παιδιού του. Είχε τέσσερα παιδιά: τον Αλθαιμένη, την Αερόπη, την Κλυμένη καιτην Απυμοσύνη. Όταν ο Αλθαιμένης πληροφορήθηκε το χρησμό, για να τον αποφύγει, έφυγε από την Κρήτη και εγκαταστάθηκε στη Ρόδο, χτίζοντας την πόλη της Κρητηνίας. Ανέβηκε στο βουνό Αττάβυρος και έχτισε ανάκτορο και ναό του Ατταβύριου Διός για να βλέπει την πατρίδα του Κρήτη από ψηλά.
Κάποτε όμως ο Κατρέας γέρασε και αποφάσισε να αφήσει το θρόνο του στον Αλθαιμένη. Έτσι ταξίδεψε μέχρι τη με το πλοίο του να τον βρεί, όμως ο Αλθαιμένης από μακρυά νόμιζε ότι ήταν πειρατές και στη συμπλοκή σκότωσε με το ακόντιο τον πατέρα του. Έτσι εκπληρώθηκε ο χρησμος. Ο Αλθαιμένης έζησε απαρηγόρητος, εως ότου πέθανε από τη λύπη του.
