Η Ναταλία Μιχαηλίδου γεννήθηκε στην Κωνσταντινούπολη. Άρχισε μαθήματα πιάνου με την μητέρα της, Πόπη Μιχαηλίδου. Πέντε ετών, έδωσε το πρώτο της ρεσιτάλ. Με υποτροφία της γαλλικής κυβερνήσεως σπούδασε στην Εcole Normale de Musique στο Παρίσι. Απεφοίτησε με το ανώτατο δίπλωμα Concertiste, με ιδιαίτερη διάκριση, σε ηλικία δεκαεπτά ετών. Συνέχισε σπουδές στο Washington University των ΗΠΑ, όπου πήρε Master. Διεκρίθη σε σειρά ρεσιτάλ γαλλικής μουσικής και της απενεμήθη η υποτροφία Albert Roussel. Βραβεύθηκε στους διεθνείς διαγωνισμούς Βαρκελώνης, Vercelli και Atheneum. Έδωσε ρεσιτάλ και συναυλίες σε πολλές πόλεις των ΗΠΑ, της Ευρώπης, της Άπω Ανατολής, της πρώην Σοβιετικής Ενώσεως. Έπαιξε σε διεθνή φεστιβάλ και συνεργάσθηκε με διεθνούς φήμης μαέστρους και σολίστ. Συνέπραξε ως σολίστ με τις κρατικές ορχήστρες Αθηνών, Θεσσαλονίκης, την Συμφωνική Ορχήστρα της ΕΡΤ, Καμεράτα, Σολίστ της Πάτρας, την Orchestre Colonne στο Παρίσι, τις συμφωνικές ορχήστρες Κωνσταντινουπόλεως, Σεούλ και Μπουσάν (Νοτίου Κορέας), Ραδιοφωνίας της Μόσχας, Santa-Cecilia κ.ά. Πολλές συναυλίες της έχουν μεταδοθεί ζωντανά από ραδιόφωνο και τηλεόραση. Παρά την εξειδίκευσή της στην γαλλική μουσική, η κυριαρχία της στο πιάνο εκτείνεται σε ευρύτατο ρεπερτόριο από την προκλασσική μέχρι την σύγχρονη εποχή. Σύγχρονοι συνθέτες της έχουν αφιερώσει έργα τους, πολλά εκ των οποίων έχει παρουσιάσει σε πρώτη παγκόσμια εκτέλεση. Συνεργάζεται με την Ελένη Καραΐνδρου και έχει συνεργασθει με τον Θεόδωρο Αγγελόπουλο. Έχει διδάξει σε σεμινάρια στην Ελλάδα, σε πανεπιστήμια του εξωτερικού και στο Ωδείο «Νίκος Σκαλκώτας». Διδάσκει στο Ωδείο Αθηνών. Από το 2001 είναι καθηγήτρια πιάνου της Ecole Normale de Musique de Paris. Συχνά συμμετέχει σε κριτικές επιτροπές διεθνών διαγωνισμών πιάνου ανά τον κόσμο. Έλαβε το βραβείον δίσκου το 2003 (Λάλον ύδωρ). Υπήρξε Πρόεδρος της ΕΡΤA Hellas (European Piano Teachers Association) επί σειρά ετών. Από το 2016 μέχρι το 2023 δίδαξε στο μεταπτυχιακό τμήμα πιάνου του Εθνικού και Καποδιστριακού Πανεπιστημίου Αθηνών.