Η ιστορία του χωριού είναι πολύ παλιά και φτάνει αιώνες πριν. Η θέση, στην οποία βρίσκεται σήμερα ο οικισμός Παλαιογρατσάνου, δεν ήταν και η αρχική. Με βάση τα όσα μαρτυρούν τα ευρήματα και τα υπάρχοντα ερείπια , ο οικισμός βρισκόταν αρχικά δυτικά της σημερινής τοποθεσίας του χωρίου και στην θέση με την ονομασία «ΓΡΑΤΣΑΝΗ». Όλα τα στοιχεία συγκλίνουν πως στην περιοχή «ΓΡΑΤΣΑΝΗ» υπήρχε οικισμός και επί Μακεδονικής εποχής ,ο οποίος καταστράφηκε μετέπειτα, πιθανότατα επί Ρωμαϊκής εποχής.
Την επωνυμία του το χωριό Παλαιογράτσανο φημολογείται πως την πήρε από τον στρατηγό «Γρατιανό», ο οποίος ήταν ένας από τους στρατηγούς του Μεγάλου Αλεξάνδρου. Αναφορές λένε πως ο εν λόγω στρατηγός , δηλ. ο «Γρατιανός», κατά την Βυζαντινή περίοδο (5ος αιώνας μ.Χ.) έχτισε δύο οικισμούς, τον πρώτο οικισμό με την ονομασία «ΓΡΑΤΙΑΝΗΝ» και τον δεύτερο οικισμό με την ονομασία «ΚΑΙΣΑΡΙΑ». Ο δεύτερος οικισμός χτίσθηκε από τον Γρατιανό κοντά στον ποταμό Αλιάκμονα και την ονομασία του «ΚΑΙΣΑΡΙΑ, την διατήρησε μέχρι και σήμερα.
Σχετικά τώρα με τον πρώτο οικισμό, ο οποίος χτίσθηκε από τον Γρατιανό με την ονομασία «ΓΡΑΤΙΑΝΗΝ», υπάρχουνστοιχεία που αναφέρονται σε έναν οικισμό , ο οποίος χτίστηκε ανατολικά της πόλης των Σερβίων. Μάλιστα τα ευρήματα, τα οποία έχουν έλθει στην επιφάνεια, είναι αδιάψευστοι μάρτυρες και αποδεικνύουν περίτρανα πως όντως υπήρχε οικισμός στη θέση «ΓΡΑΤΣΑΝΗ». Σχετικά στοιχεία και μαρτυρίες για τα λεγόμενα είναι δυνατόν να βρει κανείς στον ναό του Αγίου Δημητρίου στα ερείπια, που υπάρχουν στη θέση «ΓΡΑΤΣΑΝΗ». Τρανταχτό τεκμήριο αποτελεί και ο κώδικας , ο οποίος βρέθηκε στη μονή του Αγίου Νικάνορα στη Ζάβορδα. Στον κώδικα αυτό, ο οποίος χρονολογείται το έτος 1692 (επί του μοναχού Ιωαννίτου), υπάρχει ρητή αναφορά σε ένα χωρίο με την ονομασία «ΓΡΑΤΖΙΑΝΗ».
Στη θέση «ΓΡΑΤΣΑΝΗ» ο οικισμός παρέμεινε μέχρι τις αρχές του 19ου αιώνα και πιο συγκεκριμένα ως το 1804. Επί τουρκοκρατίας ( με τον Αλή-πασά ) οι κάτοικοι τις περιοχής δοκιμάστηκαν πολλές φορές από τις επιδρομές των Γκέκηδων. Λέγεται πως σε πολεμική επιχείρηση του Αλή–πασά κατά των αρματολών της περιοχής του Ολύμπου, οι κάτοικοι εξαναγκάστηκαν να εγκαταλείψουν την τοποθεσία «ΓΡΑΤΣΑΝΗ» και να μετοικήσουν στην νέα θέση, όπου βρίσκεται έως και σήμερα το χωρίο. Ένα μέρος των συγχωριανών εγκαταστάθηκε στη νέα αυτή θέση, όπου βρίσκεται έως σήμερα το χωρίο. Γύρω στις 30 οικογένειες μετανάστευσαν στο νέο οικισμό, ο οποίος διοικητικά πια υπαγόταν στο νέο μπέη της περιοχής έχοντας ως έδρα του τη Λάρισα. Πέρα όμως από όσους μετοίκησαν στη νέα θέση και στον νέο οικισμό, υπήρξε και ένα κύμα μεταναστών. Ένα μεγάλο ποσοστό μετανάστευσε στις γύρω περιοχές, στη Βέροια, στην Κατερίνη και σε άλλες τοποθεσίες (πρώτη εσωτερική μετανάστευση).
Ένα ιστορικό γεγονός, το οποίο διαδραματίστηκε το 1842, άλλαξε ριζικά την διοικητική και οικονομική μελλοντική πορεία του χωριού. Τότε, κάποιος από την οικογένεια «Καλοζήση», θέλοντας να αλωνίσει κάποια δεμάτια, προκειμένου να καλύψει τις ανάγκες της οικογενείας του, ήρθε σε αψιμαχία με τον εκπρόσωπο του μπέη, ο οποίος επιβλητικά του απαγόρευσε να το κάνει. Ο διαμεσολαβητής, όπως ήταν αναμενόμενο, έκανε αναφορά στον μπέη για το γεγονός, που διαδραματίσθηκε στο χωριό, έτσι ώστε να πράξει αναλόγως.
Τότε ο μπέης, έχοντας ως αφορμή το συγκεκριμένο γεγονός, αποφάσισε να προβεί στην αγοραπωλησία του χωρίου στους ίδιους τους κατοίκους. Φυσικά το συγκεκριμένο γεγονός, που έλαβε χώρα ανάμεσα στον εκπρόσωπό του και στο μέλος Καλοζήση, δεν στάθηκε καθοριστικό για την τελική γνώμη του μπέη. Σίγουρα υπήρχαν και κάποιοι άλλοι παράγοντες, που τον οδήγησαν στη λήψη αυτής της απόφασης, την αγοραπωλησία δηλ. του χωριού. Πέραν του συγκεκριμένου γεγονότος λοιπόν υπήρχαν διάφορα μικροπροβλήματα ανάμεσα στον μπέη και τους κατοίκους, τα οποία είχαν δημιουργηθεί στο παρελθόν, αλλά εξακολουθούσαν να υπάρχουν δημιουργώντας προστριβές και ταραχές. Επιπλέον, λόγω της γεωγραφικής του θέσης, το χωριό εκείνη την εποχή θεωρούνταν περιοχή δυσπρόσιτη και δύσβατη. Η είσπραξη των φόρων (το λεγόμενο χαράτσι) γινόταν με ιδιαίτερη δυσκολία και κάτω από δυσμενείς συνθήκες. Πέραν αυτού, οι εισπράξεις, τις οποίες έπαιρνε ο μπέης από τους κατοίκους, ήταν λιγοστές, καθώς το χωριό ήταν εξαιρετικά φτωχό σε έσοδα. Όλα, όσα αναφέρθηκαν παραπάνω, ανάγκασαν τον μπέη να προχωρήσει σε αλισβερίσι.
Οι Παλαιογρατσανίτες όφειλαν να σκαρφισθούν ένα τέχνασμα, είτε για να υποστούν ευνοϊκότερη μεταχείριση από τον μπέη, είτε για να πετύχουν μια καλύτερη γι’ αυτούς τιμή στην συναλλαγή. Προκειμένου λοιπόν να κατορθώσουν το καλύτερο για τους εαυτούς τους και για το χωριό τους, ήρθαν σε συνεννόηση με τους κατοίκους του χωρίου «Αγία-Κυριακή». Η συνεννόηση και το σχέδιο, που θα εκτελούσαν από κοινού οι κάτοικοι των δύο χωριών ήταν το εξής: όταν ο μπέης θα διέσχιζε το χωριό «Αγία-Κυριακή» με κατεύθυνση το Παλαιογράτσανο, οι κάτοικοι έπρεπε να διαδώσουν και να καταστήσουν σαφές στον μπέη και στους συνοδούς του, πως οι κάτοικοι του χωριού «Παλαιογρατάνου» δεν έχουν κανένα παράπονο από την διαχείριση του μπέη απέναντι τους. Απώτερος στόχος αυτού του τεχνάσματος ήταν να πετύχουν οι Παλαιογρατσανίτες να κατεβάσουν όσο το δυνατόν περισσότερο την τιμή αγοροπωλησίας του χωριού .
Και πράγματι θερμή υποδοχή επιφύλασσαν οι κάτοικοι στον μπέη, καθώς διένυε το χωριό «Αγία-Κυριακή», τιμώντας τον μάλιστα με ιδιαίτερη φιλοξενία. Το εγχείρημα πέτυχε, η συμφωνία με τον μπέη υπογράφθηκε και η τιμή ορίστηκε στα 20000 γρόσια. Το επόμενο εμπόδιο, που απασχόλησε τους κατοίκους, ήταν που θα βρεθούν τα χρήματα για την αγορά των τίτλων ιδιοκτησίας. Λόγω της οικονομικής στενότητας, που αντιμετώπιζαν οι Παλαιογρατσανίτες, αναγκάστηκαν να προσφύγουν στον δανεισμό χρημάτων από το διπλανό χωρίο, το «Καταφύγι». Ως υποθήκη έβαλαν ό,τι διέθεταν από αγροτικά τεμάχια (στη θέση «ΛΑΠΑΤΑ» και «ΜΑΥΡΗ ΡΑΧΗ»), καθώς και κήπους, οι οποίοι βρίσκονταν εντός του χωρίου. Το συμβόλαιο, το οποίο υπογράφθηκε ανάμεσα στον μπέη και τους κατοίκους του χωριού, γραμμένο στην τουρκική γλώσσα, σωζόταν στο κοινοτικό κατάστημα του χωριού μέχρι τις 11 Δεκεμβρίου του 1943, τη μέρα που κάηκε το χωριό από τα ναζιστικά στρατεύματα.
Από τα μέσα του 19ου αιώνα το χωριό έγινε κεφαλοχώρι, με κύρια χαρακτηριστικά την αύξηση του πληθυσμού και μια οικονομική άνθιση. Το έτος 1850 ανεγέρθη ο κεντρικός ναός του Αγίου Νικολάου (βασιλικού ρυθμού) στην κεντρική πλατεία του χωριού. Η αποπεράτωση του ναού ολοκληρώθηκε το 1858. Πριν την ανέγερση και ολοκλήρωση του ναού «Άγιος Νικόλαος», οι κάτοικοι εκκλησιάζονταν στο ναό της Παναγίας.