Το Πανελλήνιο Πρωτάθλημα 1958-1959 ήταν το τελευταίο που διεξήχθη με το σύστημα των ανά τοπική ένωση προκριματικών γύρων, καθώς από την επόμενη χρονιά άλλαξε η δομή του ελληνικού ποδοσφαίρου με την καθιέρωση της Α΄ Εθνικής Κατηγορίας, καθώς και των υπόλοιπων κατηγοριών που ακολούθησαν στη συνέχεια.
Ο Ολυμπιακός Πειραιώς έφτασε στην 6η συνεχόμενη κατάκτηση του πρωταθλήματος (και 15η συνολικά) μετά από μια ενδιαφέρουσα μάχη με αντίπαλο την Α.Ε.Κ..[1] Σε σχέση με την προηγούμενη χρονιά, οι ομάδες που μετείχαν στην τελική φάση του πρωταθλήματος μειώθηκαν κατά 2 (10 από 12) και προέκυψαν ως εξής:
Πρωτάθλημα Ε.Π.Σ. Αθηνών: Οι 3 πρώτες ομάδες της κατάταξης
Πρωτάθλημα Ε.Π.Σ. Πειραιώς: Οι 2 πρώτες ομάδες της κατάταξης
Περιφερειακό πρωτάθλημα: Οι 2 νικήτριες (Βορείου και Νοτίου ομίλου)
Μία επιπλέον θέση εξασφάλιζε μετά από μπαράζ μία από τις τρίτες ομάδες ΕΠΣ Πειραιά και ΕΠΣ Μακεδονίας.
Οι αγώνες της προκριματικής φάσης διεξήχθησαν από τις 7 Σεπτεμβρίου 1958 μέχρι τις 14 Ιανουαρίου 1959, ενώ της τελικής φάσης από τις 21 Ιανουαρίου μέχρι τις 21 Ιουνίου 1959. Το σύστημα βαθμολογίας ήταν: Νίκη: 3 βαθμοί - Ισοπαλία: 2 βαθμοί - Ήττα: 1 βαθμός.
1 Ο Απόλλων Καλαμαριάς έχει μία ήττα άνευ αγώνα και –1 βαθμό.
Εντός/Εκτός
ΑΡΗΣ
ΠΑΟΚ
ΑΠΟΛ
ΗΡΑ
ΘΕΡΜ
ΜΑΚ
Άρης Θεσσαλονίκης
2–1
2–1
2–0
3–3
4–0
Π.Α.Ο.Κ.
0–0
2–11
1–1
2–1
5–1
Απόλλων Καλαμαριάς
2–1
0–1
1–0
1–1
3–1
Ηρακλής Θεσσαλονίκης
2–2
1–0
1–1
3–1
2–1
Θερμαϊκός Θεσσαλονίκης
1–2
0–1
0–1
0–2
1–0
Μακεδονικός Νεάπολης
0–3
1–1
0–1
2–1
1–1
1 Ο αγώνας Π.Α.Ο.Κ. - Απόλλων Καλαμαριάς διακόπηκε στο 83' σε βάρος του Απόλλωνα Καλαμαριάς κι ενώ το σκορ ήταν 2–1 υπέρ του Π.Α.Ο.Κ.. Το σκορ παρέμεινε ως τελικό.
Σε αγώνα κατάταξης για την 3η θέση: Απόλλων Καλαμαριάς - Ηρακλής Θεσσαλονίκης 1–1. Ο Απόλλων Καλαμαριάς προκρίθηκε λόγω καλύτερης διαφοράς τερμάτων.
Διπλοί αγώνες μπαράζ μεταξύ των τρίτων ομάδων Ε.Π.Σ. Πειραιώς και Ε.Π.Σ. Μακεδονίας: Α.Ε. Νίκαιας - Απόλλων Καλαμαριάς 0–1 και 2–2.
1 Ο αγώνας Απόλλων Καλαμαριάς - Παναιγιάλειος διακόπηκε στο 70' σε βάρος του Απόλλωνα Καλαμαριάς κι ενώ το αποτέλεσμα ήταν ισόπαλο 0–0. Κατοχυρώθηκε με σκορ 0–2 υπέρ του Παναιγιάλειου.