Ο Παύλος Μελάς γεννήθηκε στις 29 Μαρτίου του 1870 στη Μασσαλία, όπου ο πατέρας του Μιχαήλ Μελάς (1833-1897) δραστηριοποιούταν ως έμπορος. Το 1886 εισήλθε στη Σχολή Ευελπίδων και εξήλθε ως ανθυπολοχαγός του Πυροβολικού στις 8 Αυγούστου του 1891. Τον επόμενο χρόνο νυμφεύτηκε τη Ναταλία Δραγούμη (1872-1973), κόρη του τραπεζίτη και πολιτικού Στέφανου Δραγούμη, με την οποία απέκτησε δύο παιδιά, τον στρατιωτικό Μιχαήλ Μελά (1894-1950) και τη χημικό Ζωή Μελά - Ιωαννίδη (1898-1996).
Υπήρξε δραστήριο μέλος της Εθνικής Εταιρείας, μιας μυστικής οργάνωσης, που είχε ως σκοπό την αναζωπύρωση του εθνικού φρονήματος και την απελευθέρωση των υπόδουλων Ελλήνων με κάθε θυσία, και έπαιξε αρνητικό ρόλο στον Ελληνοτουρκικό Πόλεμο του 1897. Με την έκρηξη του πολέμου μάχεται στα μέτωπα της Θεσσαλίας, ως διοικητής ουλαμού της 2ης Πεδινής Πυροβολαρχίας. Είναι αισιόδοξος για την έκβασή του, ώστε γράφει στους γονείς του: «...Αν ο θεός μας βοηθήση ολίγον, σύντομα θα λάβετε γράμμα μου από την Θεσσαλονίκην. Ώστε θάρρος, αγαπητοί μου γονείς, θάρρος και πεποίθησιν· διότι και αν φέρη ο διάβολος, να νικηθώμεν, θα νικηθώμεν παλικαρίσια...». Δέκα μέρες αργότερα, η κατάσταση που έχει διαμορφωθεί τον απογοητεύει και τον αηδιάζει. «Οι ηλίθιοι που φωνάζουν εναντίον του (εννοεί τον διάδοχο Κωνσταντίνο) έπρεπε να είναι εις την Λάρισσαν την επαύριο, της ατίμου, ατίμου, ατίμου φυγής μας, δια να ιδούν την κατάστασιν του στρατού και ν’ αντιληφθούν αν ήτο δυνατόν να κάμη μαζί του ένα βήμα προς τα εμπρός...» γράφει εκ νέου στους γονείς του.
Στις αρχές του 20ου αιώνα τον απασχολεί έντονα η κατάσταση στην τουρκοκρατούμενη Μακεδονία και τον ανησυχεί η δράση των κομιτατζήδων, που επιδιώκουν την προσάρτηση της Μακεδονίας στη Βουλγαρία. Τον επηρεάζει έντονα ο Μακεδόνας πεθερός του Στέφανος Δραγούμης, ενώ έχει πληροφόρηση από πρώτο χέρι από τον αδελφό της γυναίκας του Ίωνα Δραγούμη, που υπηρετεί ως υποπρόξενος στο Μοναστήρι (σημερινή Μπίτολα ΠΓΔΜ).
Τον Φεβρουάριο του 1904, μαζί με άλλους τρεις αξιωματικούς, τους λογαχούς Αλέξανδρο Κοντούλη και Αναστάσιο Παπούλα και τον ανθυπολοχαγό Γεώργιο Κολοκοτρώνη, συμμετέχει σε μυστική αποστολή στη Μακεδονία με το ψευδώνυμο Μίκης Ζέζας (Μίκης, από το όνομα του γιου του Μιχαήλ, που τον φωνάζουν χαϊδευτικά Μίκη και Ζέζας, από το όνομα της κόρης του Ζωής, που τη φωνάζουν χαϊδευτικά Ζέζα), κατόπιν εντολής της κυβέρνησης Θεοτόκη. Η ομάδα των τεσσάρων αξιωματικών, συνοδευόμενη από μακεδόνες αγωνιστές, δραστηριοποιήθηκε στη δυτική Μακεδονία, αλλά οι κινήσεις της έγιναν αντιληπτές από τους Τούρκους, οι οποίοι ζήτησαν από την ελληνική κυβέρνηση την ανάκλησή τους. Έτσι, ο Μελάς μαζί με τους τρεις άλλους αξιωματικούς επέστρεψαν στην Αθήνα στις 29 Μαρτίου.
Τον Ιούλιο, ενώ υπηρετούσε στη Σχολή Ευελπίδων, ζήτησε 20ήμερη άδεια και έκανε ένα δεύτερο ταξίδι στη Μακεδονία. Στο πλαστό διαβατήριό του αναγραφόταν το όνομα Πέτρος Δέδες και ως επάγγελμα δήλωνε ζωέμπορος. Μόλις έφθασε στην Κοζάνη συναντήθηκε με το ντόπιο ελληνικό στοιχείο και αποφασίστηκε η συγκρότηση ενόπλων σωμάτων με τη στρατολόγηση ανδρών από τις γύρω περιοχές και η ανάληψη άμεσης δράσης στη Δυτική Μακεδονία. Επέστρεψε στην Αθήνα στις 3 Αυγούστου γεμάτος αισιοδοξία για την έκβαση του Αγώνα.
Μετά από 15 ημέρες ζήτησε κι έλαβε τετράμηνη άδεια από το στράτευμα για να αναλάβει επίσημα την αρχηγία του Μακεδονικού Αγώνα στην περιοχή της Καστοριάς και του Μοναστηρίου, κατόπιν υπόδειξης του Μακεδονικού Κομιτάτου. Λίγο πριν από την αναχώρησή του εξομολογείτο στη γυναίκα του: «...Αισθάνομαι πολύ, ο δυστυχής, την ευτυχίαν που αφήνω· αισθάνομαι ότι μ’ όλον τον ανήσυχον και νευρικόν χαρακτήραν μου ο βίος ο οποίος μου αρμόζει περισσότερον είναι ο ήσυχος και ο οικογενειακός. Αλλ’ από τινος δεν ηξεύρω τι έπαθα· έγινα όργανον δυνάμεως πολύ μεγάλης, ως φαίνεται, αφού έχει την ισχύν να κατασιγάση όλα τ’ αλλα αισθήματά μου και να με ωθή διαρκώς προς την Μακεδονίαν». Και από τη Λάρισα συμπλήρωνε με νέο γράμμα προς την σύζυγό του, ωσάν να προαισθανόταν το τέλος του: «...Αναλαμβάνω αυτόν τον αγώνα με όλη μου την ψυχήν και με την ιδέαν, ότι είμαι υποχρεωμένος να τον αναλάβω. Είχα και εγώ την ακράδαντον πεποίθησιν, ότι δυνάμεθα να εργασθώμεν εν Μακεδονία και να σώσωμεν πολλά πράγματα. Έχων δε την πεποίθησιν ταύτην, έχω και υπέρτατον καθήκον να θυσιάσω το παν όπως πείσω την Κυβέρνησιν και την κοινήν γνώμην περί τούτου...».
Στις 28 Αυγούστου ο Καπετάν Μίκης Ζέζας διέβη τα σύνορα, συνοδευόμενος από αρκετούς Μακεδόνες, Λάκωνες και Κρήτες, και στα μέσα Σεπτεμβρίου στρατοπέδευσε στην περιοχή της Καστοριάς. Στις 13 Οκτωβρίου του 1904 εισήλθε στο χωριό Στάτιστα για να αναπαυτεί αυτός και οι άνδρες του. Όμως, ο Βούλγαρος αρχικομιτατζής Μήτρος Βλάχος, προκειμένου να τον βγάλει από τη μέση, ειδοποίησε τις οθωμανικές αρχές. Επί τόπου κατέφθασε ισχυρό στρατιωτικό απόσπασμα, αποτελούμενο από 150 άνδρες και στη συμπλοκή που ακολούθησε, ο Παύλος Μελάς τραυματίστηκε σοβαρά στην οσφυϊκή χώρα και μετά από μισή ώρα άφησε την τελευταία του πνοή.
Το κεφάλι του αποκόπηκε από τους συμπολεμιστές του και τάφηκε στο ναό της Αγίας Παρασκευής στο Πισοδέρι. Το σώμα του παραδόθηκε από τις οθωμανικές αρχές στον μητροπολίτη Καστοριάς Γερμανό (Καραβαγγέλη) και τάφηκε στον βυζαντινό ναό των Ταξιαρχών στην Καστοριά, όπου αναπαύεται και η κάρά του από το 1950. Στον ίδιο ναό έχει ταφεί και η σύζυγός του Ναταλία, κατ’ επιθυμίαν της.
Ο θάνατος του Παύλου Μελά έγινε γνωστός στην Αθήνα στις 18 Οκτωβρίου και συγκλόνισε την κοινή γνώμη, λόγω του ακέραιου και αγνού χαρακτήρα του ανδρός, αλλά και του γνωστού ονόματος της οικογένειάς του, που είχε μεγάλους δεσμούς με τη Μακεδονία και την κοινωνία των Αθηνών. Η θυσία του σηματοδότησε την ουσιαστική έναρξη του Μακεδονικού Αγώνα, που κορυφώθηκε με τους Βαλκανικούς Πολέμους του 1912-1913.
