Ο Παύλος Μελάς, ένα από τα επτά παιδιά του Μιχαήλ Μελά και της Ελένης, γεννήθηκε στις 29 Μαρτίου του 1870 στη Μασσαλία, όπου ο πατέρας του δραστηριοποιούταν ως έμπορος. Φοίτησε στη Σχολή Ευελπίδων και εξήλθε ως ανθυπολοχαγός του Πυροβολικού τον Αύγουστο του 1891. Τον επόμενο χρόνο νυμφεύτηκε τη Ναταλία Δραγούμη, κόρη του τραπεζίτη και πολιτικού Στέφανου Δραγούμη, με την οποία απέκτησε δύο παιδιά, τον στρατιωτικό Μιχαήλ Μελά και τη χημικό Ζωή Μελά – Ιωαννίδη.

Στις αρχές του 20ου αιώνα τον απασχολεί έντονα η κατάσταση στην τουρκοκρατούμενη Μακεδονία και τον ανησυχεί η δράση των κομιτατζήδων, που επιδιώκουν την προσάρτηση της Μακεδονίας στη Βουλγαρία. Τον επηρεάζει έντονα ο Μακεδόνας πεθερός του, ενώ έχει πληροφόρηση από πρώτο χέρι από τον αδελφό της γυναίκας του Ίωνα Δραγούμη, που υπηρετεί ως υποπρόξενος στο Μοναστήρι.

Τον Φεβρουάριο του 1904, μαζί με άλλους τρεις αξιωματικούς, τους λογαχούς Αλέξανδρο Κοντούλη και Αναστάσιο Παπούλα και τον ανθυπολοχαγό Γεώργιο Κολοκοτρώνη, συμμετέχει σε μυστική αποστολή στη Μακεδονία με το ψευδώνυμο Μίκης Ζέζας (Μίκης, από το όνομα του γιου του Μιχαήλ, που τον φωνάζουν χαϊδευτικά Μίκη και Ζέζας, από το όνομα της κόρης του Ζωής, που τη φωνάζουν χαϊδευτικά Ζέζα), κατόπιν εντολής της κυβέρνησης Θεοτόκη. Η ομάδα των τεσσάρων αξιωματικών, συνοδευόμενη από μακεδόνες αγωνιστές, δραστηριοποιήθηκε στη δυτική Μακεδονία, αλλά οι κινήσεις της έγιναν αντιληπτές από τους Τούρκους, οι οποίοι ζήτησαν από την ελληνική κυβέρνηση την ανάκλησή τους. Έτσι, ο Μελάς μαζί με τους τρεις άλλους αξιωματικούς επέστρεψαν στην Αθήνα στις 29 Μαρτίου.

Τον Ιούλιο, ενώ υπηρετούσε στη Σχολή Ευελπίδων, ζήτησε 20ήμερη άδεια και έκανε ένα δεύτερο ταξίδι στη Μακεδονία. Στο πλαστό διαβατήριό του αναγραφόταν το όνομα Πέτρος Δέδες και ως επάγγελμα δήλωνε ζωέμπορος. Μόλις έφθασε στην Κοζάνη συναντήθηκε με το ντόπιο ελληνικό στοιχείο και αποφασίστηκε η συγκρότηση ενόπλων σωμάτων με τη στρατολόγηση ανδρών από τις γύρω περιοχές και η ανάληψη άμεσης δράσης στη Δυτική Μακεδονία. Επέστρεψε στην Αθήνα στις 3 Αυγούστου γεμάτος αισιοδοξία για την έκβαση του Αγώνα.

Μετά από 15 ημέρες ζήτησε κι έλαβε τετράμηνη άδεια από το στράτευμα για να αναλάβει επίσημα την αρχηγία του Μακεδονικού Αγώνα στην περιοχή της Καστοριάς και του Μοναστηρίου, κατόπιν υπόδειξης του Μακεδονικού Κομιτάτου.

Στις 28 Αυγούστου ο Καπετάν Μίκης Ζέζας διέβη τα σύνορα, συνοδευόμενος από αρκετούς Μακεδόνες, Λάκωνες και Κρήτες, και στα μέσα Σεπτεμβρίου στρατοπέδευσε στην περιοχή της Καστοριάς.

Στις 13 Οκτωβρίου του 1904 εισήλθε στο χωριό Στάτιστα (σημερινός Μελάς Καστοριάς) για να αναπαυτεί αυτός και οι άνδρες του. Όμως, ο Βούλγαρος αρχικομιτατζής Μήτρος Βλάχος, προκειμένου να τον βγάλει από τη μέση, ειδοποίησε τις οθωμανικές αρχές. Επί τόπου κατέφθασε ισχυρό στρατιωτικό απόσπασμα, αποτελούμενο από 150 άνδρες και στη συμπλοκή που ακολούθησε, ο Παύλος Μελάς τραυματίστηκε σοβαρά στην οσφυϊκή χώρα και μετά από μισή ώρα άφησε την τελευταία του πνοή.

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

Ο θάνατος του Παύλου Μελά έγινε γνωστός στην Αθήνα στις 18 Οκτωβρίου και συγκλόνισε την κοινή γνώμη, λόγω του ακέραιου και αγνού χαρακτήρα του ανδρός, αλλά και του γνωστού ονόματος της οικογένειάς του, που είχε μεγάλους δεσμούς με τη Μακεδονία και την κοινωνία των Αθηνών. Η θυσία του σηματοδότησε την ουσιαστική έναρξη του Μακεδονικού Αγώνα, που κορυφώθηκε με τους Βαλκανικούς Πολέμους του 1912-1913.