Ο Ματθαίος Τσολακίδης γεννήθηκε στον Πόντο το 1910 ήταν ο δευτερότοκος γιος της οικογένειας του Παύλου και της Μαρίας, το γένος Μυρωνίδη. Είχε προηγηθεί ο Μιχαήλ το 1906, ενώ αργότερα ήρθε ο Τριαντάφυλλος το 1914. Ο πατέρας του πέθανε στα καταναγκαστικά έργα των Τούρκων, στα απάνθρωπα τάγματα εργασίας ή αλλιώς “Αμελέ Ταμπουρού” Η μητέρα Μαρία θα έρθει στην Ελλάδα, με τα τρία της παιδιά το 1923, με την ανταλλαγή των πληθυσμών.

Ο Ματθαίος φοίτησε στο δημοτικό σχολείο Σχιστολίθου και στην συνέχεια στο εξατάξιο Γυμνάσιο Σιδηροκάστρου. Το 1935 νυμφεύεται την Μαρία Γρεασίδου του Γεωργίου και της Θεοδώρας και το 1936 θα γεννηθεί η κόρη τους Ευθυμία.

Το Σεπτέμβριο του 1936 εισάγεται μετά από εξετάσεις στην Παιδαγωγική Ακαδημία Θεσσαλονίκης και στις 22 Ιουνίου 1938 παρουσία επιτροπής καθηγητών δίνει εξετάσεις με υποδειγματική διδασκαλία στην Δ’ Δημοτικού με επιτυχία. Το θέμα που του δόθηκε προς ανάπτυξη ήταν ιστορικό με τίτλο "Οι Ρωμαίοι κυριεύουν την Ελλάδα" Σύμπτωση!!!... Μετά τρία χρόνια το 1941 θα βρεθεί να πολεμάει τους Ιταλούς (Ρωμαίοι) οι οποίοι θα προσπαθήσουν να κυριεύσουν την Ελλάδα… Την 1η Ιουλίου 1938 κρίνεται άξιος μαζί με άλλους 38 συμφοιτητές του και παραλαμβάνει το πτυχίο του διδασκάλου. Διδάσκει στο Δημοτικό σχολείο Αηδονοχωρίου Σερρών, ενώ δίδαξε για ένα μικρό διάστημα και στο Δημοτικό σχολείο Σχιστολίθου.

Στις 13 Απριλίου 1939 κατατάσσεται στη Σχολή Εφέδρων Αξιωματικών Πεζικού Σύρου, από όπου θα αποφοιτήσει ευδοκίμως στις 12 Ιανουαρίου 1940.