Οι οικοδόμοι είναι άνθρωποι που στέκουν ανάμεσα ουρανού και γης, χτίζουν και τραγουδάνε. Με τα χέρια τους χτίζουν τα σπίτια των ανθρώπων, με τα τραγούδια τους χτίζουν όνειρα και σκάλες, που οδηγούν στον ουρανό. Ο Απόστολος Νικολαϊδης ήταν οικοδόμος. Το όνειρό του ήτανε να γίνει ένας επαγγελματίας τραγουδιστής.

Οι δεκαετίες του ’50 και του ‘60 ήταν η εποχή των οικοδόμων - τραγουδιστών: Γιάννης Τζιβάνης, Στέλιος Καζαντζίδης, Στράτος Κύπριος και πολλοί άλλοι... Όταν ο εργάτης γίνει επαγγελματίας τραγουδιστής, τα λαϊκά τραγούδια που λέει αποκτούν μιαν άλλη αυθεντικότητα. Τα βιώματα της φτώχιας, της στέρησης και της βιοπάλης γίνονται συναισθήματα της ψυχής και από την ψυχή περνούνε μέσα στις φωνητικές χορδές, χρωματίζουν τις λέξεις, τις συλλαβές και τις μελωδίες με τα κατάλληλα αυθεντικά χρώματα: το χρώμα του λυγμού, του παράπονου, της διαμαρτυρίας, της διεκδίκησης... Ο Απόστολος Νικολαΐδης ανήκει κι αυτός στην ομάδα των οικοδόμων - τραγουδιστών.

Γεννημένος το 1938 στη Δράμα, μετακομίζει μαζί με την οικογένειά του στη Θεσσαλονίκη. Η οικογένειά του δεν έχει ψωμί για να φάει, δεν έχει ξύλα για να ζεσταθεί. Κι όταν δεν έχεις να φας, δεν έχεις το μυαλό σου στο σχολείο και στα μαθήματα, όπως χαρακτηριστικά δήλωνε ο ίδιος. Έτσι τον κέρδισε ο προφορικός πολιτισμός - το Λαϊκό Τραγούδι, που ερχότανε από τα βάθη των αιώνων. Από δεκατριών χρονών παιδί (1951) δούλευε στις οικοδομές, πρώτα μαζεύοντας πρόκες, μετά κουβαλώντας μαδέρια και μπετόν στην ωμοπλάτη και στο τέλος καλουπατζής - ξυλουργός μπετόν αρμέ, όπως αναγράφεται στο εργατικό του βιβλιάριο, στα 1959. Γι’ αυτό και απόκτησε αθλητικό παράστημα, επειδή έκανε γυμναστική από μικρός, όπως δηλώνει πάλι ο ίδιος. Κι εδώ φαίνεται το σαρκαστικό χιούμορ του Απόστολου Νικολαϊδη, ένα χιούμορ που θα εκδηλωθεί αργότερα με τη μορφή μάγκικου ύφους στα τραγούδια του. Παράλληλα ο έφηβος Αποστόλης, που «από την κοιλιά της μάνας του» και «από την κούνια του» ακόμα τραγουδούσε, ασχολείται και με τη μουσική. Το μαντολίνο και ύστερα την κιθάρα που γρατζουνούσε, του τα σπάσανε οι γονείς του, σε μια προσπάθεια να τον αποθαρρύνουνε απ’ το να ασχολείται με το τραγούδι, που κατά τη γνώμη τους και με τα δεδομένα της εποχής δεν μπορούσε να θρέψει μια φτωχή οικογένεια. Όμως ο Αποστόλης επέμενε και μαζί με δυο φίλους του σχημάτισαν ένα τρίο χωρίς όνομα και κάνανε καντάδες στα ...βουνά και στις ερημιές, αφού τότε η περιοχή της Άνω Τούμπας, όπου μένανε, είχε ελάχιστα σπίτια.

Τα κανταδόρικα και ελαφρά τραγούδια, που τραγουδούσε εκείνη την εποχή, με τους πλατειασμούς και τις γλυκερότητές τους, θα προικίσουνε τη φωνή του Νικολαϊδη με μια πλατειαστική, κοροϊδευτική διάθεση, που θα εκδηλωθεί κι αυτή στα μάγκικα τραγούδια του, διαμορφώνοντας αργότερα το ιδιαίτερο μάγκικο χρώμα αυτού του τραγουδιστή. Όμως όταν άκουσε από δίσκους τη φωνή του Καζαντζίδη, ομολογεί ότι όλα άλλαξαν μέσα του. Κατάλαβε ότι τα ερωτικά και κοινωνικά τραγούδια στο ύφος Καζαντζίδη ήταν καμωμένα για να εκφράζουν όλο τον κόσμο. Κι έτσι εντάχθηκε στη μεγάλη του Καζαντζίδη σχολή (απ’ τον οποίο είχε πάντα κάτι να διδαχτεί, όπως ομολογεί και πάλι ο ίδιος) σαν ένα ξεχωριστό μέλος της. Όπως ο Σαούλ βρήκε το φως του ακούγοντας τη φωνή του Ιησού στο δρόμο προς την Εμμαούς, όπως ο Μπιθικώτσης από το Ελαφρό Τραγούδι που τραγουδούσε μέχρι τότε μπήκε στο δρόμο του Λαϊκού, ακούγοντας Μάρκο Βαμβακάρη, έτσι κι ο Απόστολος Νικολαΐδης ακολούθησε τη λεωφόρο του Λαϊκού Τραγουδιού, ακούγοντας τη φωνή του Στέλιου Καζαντζίδη από τους δίσκους των 78 στροφών.

Το 1961 κατέβηκε στην Αθήνα, με σκοπό να πραγματοποιήσει το όνειρό του. Στο στούντιο της Columbia, με συνοδεία μπουζουκιών του Κώστα Παπαδόπουλου και του Λάκη Καρνέζη, τραγουδάει δοκιμαστικά, προκειμένου να εγκριθεί η φωνή του, το «Δυο πόρτες έχει η ζωή». Ο Στέλιος Καζαντζίδης κι όσοι άλλοι βρίσκονταν εκείνη την ώρα στο στούντιο ενθουσιάζονται κι ο Απόστολος υπογράφει συμβόλαιο με τις δίδυμες εταιρίες Columbia και His Master’ s Voice μέχρι το 1967. Τραγουδάει σε δίσκους 45 στροφών Τσιτσάνη, Γενίτσαρη, Χιώτη, Καλδάρα, Λαύκα, Κλουβάτο, Καραμπεσίνη, αλλά τα τραγούδια που του παραχωρούσε η εταιρεία δεν είχανε το προφίλ της επιτυχίας. Έτσι από τη μια πόρτα της Columbia μπήκε το 1961 κι από την άλλη βγήκε το 1967. Τότε υπέγραψε συμβόλαιο με τη μικρή εταιρεία Βεντέτα, όπου τραγούδησε τέσσερα τραγούδια του Χρίστου Κολοκοτρώνη. Παράλληλα με τη δισκογραφία, ο Νικολαΐδης τραγουδούσε και στα νυχτερινά κέντρα, άλλοτε με Καζαντζίδη - Μαρινέλλα κι άλλοτε με Καλδάρα, Λαύκα, Παπαϊωάννου κι άλλους προγενέστερους λαϊκούς συνθέτες και δεξιοτέχνες. Ο σεβασμός του απέναντι στις προσωπικότητες και στο έργο των παλιότερων συνθετών είναι αυτός που θα οδηγήσει αργότερα το Νικολαΐδη να τραγουδήσει τα μάγκικα τραγούδια (απαγορευμένα και μη) κι έτσι να γίνει ο γεφυροποιός που συνδέει τις εποχές Τούντα και Βαμβακάρη με την εποχή Στέλιου Καζαντζίδη.

Στα 1968 μια καλλιτεχνική περιοδεία του τον οδηγεί στο Τορόντο του Καναδά, όπου συνεργάζεται με τον κορυφαίο δεξιοτέχνη του μπουζουκιού Χάρη Λεμονόπουλο για δυο χρόνια. Από εκεί μετακινήθηκε στις ΗΠΑ, όπου εγκαταστάθηκε στη Νέα Υόρκη, αργότερα παντρεύτηκε κι απόκτησε δυο κόρες. Ωστόσο η συνεργασία του με το Λεμονόπουλο θα αποδώσει ένα σπουδαίο δισκογραφικό καρπό: τον πρώτο δίσκο μακράς διαρκείας του Απόστολου Νικολαΐδη, με τον τίτλο «Γυάλινος κόσμος» (1969). Εδώ φαίνεται καθαρά η τάση του Απόστολου Νικολαΐδη να γεφυρώσει την εποχή Βαμβακάρη με την εποχή Καζαντζίδη σε ένα ενιαίο και ομοούσιο είδος που είναι το Λαϊκό Τραγούδι. Το εμβληματικό τραγούδι του Μάρκου Βαμβακάρη «Όλοι οι ρεμπέτες του ντουνιά», που κατά κάποιο τρόπο αποτελεί το μανιφέστο της ρεμπετιάς, δηλαδή της μαγκιάς, συνυπάρχει με το «Γυάλινο κόσμο» (Καλδάρα - Παπαγιαννοπούλου), που αποτελεί ένα κοινωνικό μανιφέστο, με διάθεση να αντικατασταθεί ένα άδικο κοινωνικό σύστημα με ένα άλλο δικαιότερο. Σημειωτέον ότι ο Απόστολος Νικολαΐδης έκανε μια εξαίρετη ερμηνεία, ανανεώνοντας αυτό το τραγούδι, μετά την πρώτη ατυχή εκτέλεση του Βασίλη Βλάση (γύρω στα 1960) και πάντως δυο χρόνια πριν από τη θαυμάσια επανεκτέλεση του Στέλιου Καζαντζίδη (1973).