Στα τέλη του 19ου αιώνα η Οθωμανική Αυτοκρατορία ήρθε σε συμφωνία με Αυστρογερμανούς επενδυτές για την εγκατάσταση ενός πλέγματος περιφερειακών σιδηροδρομικών γραμμών, που θα συντελούσε στην εύκολη μεταφορά πρώτων υλών και βιομηχανικών προϊόντων. Οι Αυστρογερμανοί προσπαθούσαν να δημιουργήσουν ένα σιδηροδρομικό άξονα Βιέννης – Θεσσαλονίκης μέσω Βοσνίας. Στα πλαίσια αυτά κινήθηκε η πρότασή τους για τη σιδηροδρομική σύνδεση Θεσσαλονίκης – Μοναστηρίου (Μπιτόλια). Οι συζητήσεις κράτησαν περισσότερο από ένα χρόνο και τελικά η εκχώρηση του δικαιώματος κατασκευής και εκμετάλλευσης της γραμμής για 99 έτη ανατέθηκε με αυτοκρατορικό φιρμάνι (27-10-1890) στην Deutsche Bank του Βερολίνου, η δε συμφωνία υπογράφηκε στις 28-10-1890.

Οι όροι της προέβλεπαν υποβολή οριστικής μελέτης του πρώτου τμήματος της γραμμής (Θεσσαλονίκη – Βέροια) μέσα σε έξι (6) μήνες από την υπογραφή της συμφωνίας και έναρξη των εργασιών εκτέλεσης σε δεκαπέντε (15) μήνες. Η αποπεράτωση του συνολικού μήκους της γραμμής έπρεπε να γίνει σε τρεισήμισι χρόνια το αργότερο και ο σταδιακός έλεγχος της καλής εκτέλεσης των όρων της σύμβασης θα γινόταν από επιτροπή, που θα όριζε το οθωμανικό δημόσιο. Για την κατασκευή συμφωνήθηκε να χρησιμοποιηθεί γραμμή πλάτους 144 εκατοστών – αντί της στενής των 100 εκ.- παρ’ όλη την οικονομική επιβάρυνση στο σύνολο του δικτύου, με κριτήριο τη μελλοντική σύνδεση με το ευρωπαϊκό δίκτυο. Το μέσο κόστος κατασκευής ορίστηκε με βάση την προμελέτη σε 113.000 φρ. ανά χιλιόμετρο γραμμής, ποσό που περιλάμβανε όλα τα έξοδα μελέτης, σύνταξης σχεδίων εφαρμογής, απαλλοτριώσεις εδαφών, κατασκευή του δικτύου και των σταθμών, προμήθεια ακινήτου και σταθερού υλικού, τηλεγραφικές εγκαταστάσεις και έργα υποδομής.

Η εκτέλεση των εργασιών, που ήταν δύσκολη εξαιτίας της γεωμορφολογίας της περιοχής και των κλιματολογικών συνθηκών, απαίτησε την πραγματοποίηση αρκετών εξειδικευμένων τεχνικών έργων. Το «στρώσιμο» της γραμμής ξεκίνησε από τη Θεσσαλονίκη. Από το 28,8 χλμ μέχρι το σταθμό της Αλεξάνδρειας (Guida) στο 44,1 χλμ. κατασκευάστηκαν τρείς γέφυρες, από τις οποίες η μία είχε άνοιγμα 72 μ., πάνω από τον ποταμό Λουδία (Καρά Ασμάκ). Από το 44,1 χλμ μέχρι το σταθμό της Βέροιας (Καραφέρια) στο 67,5 χλμ, δώδεκα μικρές γέφυρες συνολικού ανοίγματος 200 μ. περίπου. Από το 67,5 χλμ. μέχρι το σταθμό της Νάουσας (Άγουστος) στο 79,1 χλμ., τρείς μικρές γέφυρες.

Η εταιρία ανέλαβε επίσης την κατασκευή των κτιρίων όλων των σταθμών εκτός από της Θεσσαλονίκης. Οι εξυπηρετούμενοι σταθμοί ήταν στη Θεσσαλονίκη, Σίνδο (Τεκελή), ΄Αδενδρο (Κιρτζαλάρ), Αλεξάνδρεια (Γιδάς), Βέροια (Καραφέρια), Νάουσα (Άγουστος), Σκύδρα (Βερτεκόπ).

Για την εγκατάσταση της γραμμής, η κατασκευάστρια εταιρία υποχρεώθηκε να απαλλοτριώσει τα εδάφη απ’ όπου θα περνούσε η χάραξη, καταβάλλοντας αποζημίωση στους γαιοκτήμονες μέχρι 6,67 χρυσά πιάστρα το τετραγωνικό μέτρο. Όμως κατά το δεύτερο έτος κατασκευής (1892) οι τιμές που ζητήθηκαν από τους γαιοκτήμονες ήταν διπλάσιες και μερικές φορές τριπλάσιες από τα αρχικά μεγέθη. Η εκμετάλλευση του σιδηρόδρομου ανατέθηκε στην «Compagnie d’ Exploitation des Chemins de fer orientaux», που ανέλαβε και την καταβολή όλων των εξόδων λειτουργίας.

Το πρώτο τμήμα της γραμμής, μήκους 97 χλμ, κάλυψε την απόσταση Θεσσαλονίκη – Σκύδρα (Βερτεκόπ) και εγκαινιάσθηκε στις 9 Δεκεμβρίου 1892 με ιδιαίτερη επισημότητα και δόθηκε για εκμετάλλευση.

Από τη Θεσσαλονίκη αναχωρούσε καθημερινά η αμαξοστοιχία στις 06.50 κι έφθανε στις 08.00 στο Κερτζαλάρ, στις 08.39 στο Γκουίντα (Αλεξάνδρεια), στις 09.41 στην Καραφέρια, στις 10.12 στην Άγουστος (Νάουσα) και στις 10.49 στο Βερτεκόπ. Από κει αναχωρούσε η αμαξοστοιχία για τη Θεσσαλονίκη στις 12.19 κι έφθανε στις 12.52 στην Άγουστος, στις 13.28 στην Καραφέρια, στις 14.25 στο Γκουίντα, στις 15.04 στο Κερτζαλάρ και στις 16.09 στη Θεσσαλονίκη.

Η λειτουργία του θεωρήθηκε ενδεικτική της όλης μετέπειτα εξελικτικής πορείας του τοπικού αυτού δικτύου και αναλύθηκε με μεγάλη λεπτομέρεια από το Στατιστικό Τμήμα του Γραφείου Κινήσεως. Τα ενθαρρυντικά πορίσματα της έκθεσης ισολογισμού 1893 που έδειξαν διακίνηση 43.555 επιβατών, 21.564 τόνων εμπορευμάτων, έσοδα 4.617,62 χρυσών φράγκων ανά χλμ. και έξοδα 3.123,59 χρυσών φράγκων ανά χλμ., ενθάρρυναν το διοικητικό συμβούλιο, που επιτάχυνε τη διαδικασία εκτέλεσης των έργων από Σκύδρα έως Μοναστήρι το 1894.