Ο Στρυμόνας ήταν ποτάμιος θεός, γιος του Ωκεανού και της Τηθύος. Σύμφωνα με κάποιες μυθολογικές εκδοχές, ήταν γιος του Άρη και της Ηλίκης. Ήταν πατέρας του Ρήσου και της Σήτης, η οποία αναφέρεται ως αδελφή του. Η μητέρα του Ρήσου ήταν κάποια από τις Μούσες, το όνομα της οποίας παραδίδεται διαφορετικό ανάλογα με τις πηγές. Από τη Νέαιρα ο Στρυμόνας απέκτησε την Ευάδνη, ενώ παιδιά του ήταν η Τερείνη, ο Βράγγας, ο Όλυνθος, ο Βορέας και η Ροδόπη, χωρίς όμως να γνωρίζουμε τις μητέρες τους. Αρχικά ο ποταμός ονομαζόταν Κόνοζος. Ο ηγεμόνας της περιοχής Παλαιστίνος, γιος του Ποσειδώνα, ενώ βρισκόταν σε εμπόλεμη κατάσταση με τις γειτονικές φυλές, αρρώστησε και αναγκάστηκε να στείλει στον πόλεμο ως στρατηγό τον γιο του, Αλιάκμονα. Ο Αλιάκμονας σκοτώθηκε και ο Παλαιστίνος μην μπορώντας να αντέξει τον χαμό τoυ, πνίγηκε στον ποταμό Κόνοζο, ο οποίος μετονομάστηκε για αυτό τον λόγο σε Παλαιστίνος. Ωστόσο, και ο Στρυμόνας , όταν πληροφορήθηκε τον θάνατο του γιου του, Ρήσου, ο οποίος σκοτώθηκε μπροστά από τα τείχη της Τροίας, από τη στενοχώρια του έπεσε στον ποταμό Παλαιστίνο, ο οποίος μετονομάστηκε σε Στρυμόνας. Μια άλλη εκδοχή του μύθου αναφέρει και τη μάχη του Στρυμόνα με τον Ηρακλή. Ο τελευταίος, όταν επέστρεφε από την Ισπανία με τα βόδια του Γηρυόνη, δεν μπορούσε να διασχίσει τον ποταμό Στρυμόνα, γιατί δεν υπήρχε πέρασμα. Τελικά, ο Ηρακλής κατάφερε να περάσει στην απέναντι όχθη ρίχνοντας τεράστιους βράχους μέσα στο ποτάμι.
