Η Μελίνα Παιονίδου γεννήθηκε στην Κύπρο.

Σπούδασε στο ΚΟΝΣΕΡΒΑΤΟΡΙΟ TCHAIKOVSKY της Μόσχας στον κλάδο «Διεύθυνσης Χορωδίας» (MASTER OF ARTS-CHORAL CONDUCTING). Έλαβε μέρος σε σεμινάρια διεύθυνσης χορωδίας του Γερμανού μαέστρου Helmut Rilling στη Ρωσία, Γερμανία και Αμερική. Το Σεπτέμβριο του 1993 μετά από πρόσκληση του Μίκη Θεοδωράκη εργάστηκε ως μαέστρος στη χορωδία της ΕΡΤ. Από το καλοκαίρι του 1995 εργάζεται στο Εθνικό Θέατρο ως μουσικοδιδάσκαλος. Έχει στο ενεργητικό της μουσικές διδασκαλίες, επιμέλειες και φωνητικές επεξεργασίες. Από το 1996 μέχρι και σήμερα είναι καθηγήτρια μουσικής στην Ανώτερη Δραματική Σχολή του Εθνικού Θεάτρου. Έχει συνεργαστεί με πολλούς σκηνοθέτες και συνθέτες σε πάνω από 100 έργα εκ των οποίων τα 35 στο αρχαίο θέατρο της Επιδαύρου.

Με συμμετοχές όπως Σρεκ, το μιούζικαλ | Θεατρική Παράσταση (2014), Φιλουμένα | Θεατρική Παράσταση (2015), Πιάφ | Θεατρική Παράσταση (2015), Ο Λάκκος της Αμαρτίας | Θεατρική Παράσταση (2015), Κρίμα που είναι πόρνη | Θεατρική Παράσταση (2015), Το πένθος ταιριάζει στην Ηλέκτρα | Θεατρική Παράσταση (2013).