Γεννήθηκε στη Μασσαλία της Νότιας Γαλλίας . Η καταγωγή της οικογένειάς του ήταν από τον Παρακάλαμο Πωγωνίου της Περιφερειακής Ενότητας Ιωαννίνων. Μετά τη μετακίνηση της οικογένειας στην Αθήνα, σπούδασε στη Στρατιωτική Σχολή Ευελπίδων απ' όπου αποφοίτησε ως ανθυπολοχαγός του πυροβολικού το 1891. Φέροντας τύψεις για την έκβαση του πολέμου του 1897 συμμετείχε από τους πρώτους στο ιδρυθέν το 1900 Μακεδονικό κομιτάτο για την εμψύχωση του απογοητευμένου ελληνικού πληθυσμού της Μακεδονίας και σε αντίδραση στη δράση των Βουλγάρων κομιτατζήδων. Έτσι από τον Φεβρουάριο του 1904 ο Παύλος Μελάς έσπευσε με άλλους τρεις αξιωματικούς, τους Α. Κοντούλη, Α. Παπούλα και Γ. Κολοκοτρώνη, προς επιτόπια μελέτη της κατάστασης. Αποτυγχάνοντας σε εκείνη την πρώτη προσπάθεια, επανήλθε τον Ιούλιο του ίδιου έτους οπότε και εισήλθε στη Μακεδονία ως ζωέμπορος με το όνομα "Πέτρος Δέδες". Μετά 20ήμερη παραμονή συναντήθηκε με τον Λάμπρο Κορομηλά στη Θεσσαλονίκη ανταλλάσσοντας σκέψεις για ανάληψη επιχειρήσεων και στη συνέχεια επέστρεψε στην Αθήνα.
Στις 18 Αυγούστου όταν όλα ήταν έτοιμα κατά το σχέδιο ο Παύλος Μελάς με το επιχειρησιακό όνομα Καπετάν Μίκης Ζέζας, επικεφαλής σώματος εκ 35 μόλις ανδρών, που το αποτελούσαν Μακεδόνες, Μανιάτες και Κρητικοί, ανέλαβε την αρχηγία του Μακεδονικού αγώνα ενάντια στους Βούλγαρους και εισήλθε ένοπλα στα Μακεδονικά εδάφη με την εντολή να ασκεί καθήκοντα αρχηγού και στις μικρότερες ομάδες που δρούσαν εν τω μεταξύ στη περιφέρειες Μοναστηρίου και Καστοριάς. Πληροφορηθέντες οι Τούρκοι από διάφορους καταδότες περί της εισόδου και της δράσης του Παύλου Μελά έθεσαν προς καταδίωξή του πολυάριθμο τουρκικό απόσπασμα. Παρά τις συνεχείς διώξεις του Οθωμανικού στρατού ο Παύλος Μελάς άρχισε ν΄ αποδεκατίζει τις βουλγαρικές ομάδες με βάση τα χωριά Λιγκοβάνη και Λίχυβο. Όμως στις 13 Οκτωβρίου 1904 βρισκόμενος στα Στάτιστα και προδομένος από την βουλγάρικη συμμορία του Μήτρου Βλάχου περικυκλώθηκε από Τουρκικό απόσπασμα 150 ανδρών. Μετά από δίωρη λυσσαλέα μάχη διέταξε αιφνίδια έξοδο τεθείς επικεφαλής των ανδρών του. Στην επιχείρηση αυτή τραυματίσθηκε θανάσιμα στην οσφυϊκή χώρα και πέθανε μετά από μισή ώρα στα χέρια του φίλου του, Γεώργιο Στρατινάκη. Η τελευταία του φράση πριν ξεψυχήσει ήταν:
"Βούλγαρος να μη μείνει"
Γύρω από το σώμα του νεκρού Π. Μελά εκτυλίχθηκε μια διπλωματική επιχείρηση για την παραλαβή και ενταφιασμό του. Οι Έλληνες δεν ήθελαν να γίνει γνωστό στους Τούρκους ποιος ήταν ο νεκρός, και συγκεκριμένα ότι ήταν Έλληνας αξιωματικός, διότι αυτό θα δημιουργούσε διπλωματική κρίση. Αρχικά ο νεκρός θάφτηκε από τους χωρικούς έξω από τη Στάτιστα ενώ οι Τούρκοι δεν γνώριζαν την ταυτότητά του. Αργότερα ο προεστός της Στάτιστας ονόματι Ντίνας απεσταλμένος της ελληνικής πλευράς (πιθανώς του Μητροπολίτη Καστοριάς Γερμανού Καραβαγγέλη ή του οπλαρχηγού Κύρου) επιχείρησε να ξεθάψει και να μεταφέρει αλλού τον νεκρό. Στο μεταξύ όμως ο θάνατος του Μελά είχε μαθευτεί στην Αθήνα και η Τουρκική πρεσβεία στην Αθήνα ειδοποίησε τις Τουρκικές Αρχές της Θεσσαλονίκης να βρουν το πτώμα ώστε να το χρησιμοποιήσουν ως απόδειξη της Ελληνικής επέμβασης σε Τουρκική επικράτεια. Έτσι, ενώ ο Ντίνας έκανε την εκταφή εμφανίστηκε Τουρκικός στρατός. Τότε έκοψε βιαστικά το κεφάλι του νεκρού και έφυγε. Το κεφάλι τάφηκε μπροστά στην Ωραία Πύλη του Ναού της Αγίας Παρασκευής στο χωριό Πισοδέρι ενώ οι Τούρκοι πήραν το ακέφαλο σώμα και το πήγαν στην Καστοριά για αναγνώριση. Ο Γερμανός Καραβαγγέλης, που γνώριζε τα πάντα, κινητοποίησε τη νεολαία της Καστοριάς που περικύκλωσε το Διοικητήριο και απαιτούσε να τους δοθεί το σώμα "κάποιου Ζέζα" που ήταν Έλληνας. Ο Μητροπολίτης, προειδοποιώντας ότι μπορεί να συμβούν ταραχές που θα έβλαπταν την ειρηνική συμβίωση Τούρκων και Ελλήνων κατάφερε να του δοθεί το σώμα το οποίο και τάφηκε στο παρεκκλήσιο των Ταξιαρχών κοντά στο Μητροπολιτικό Μέγαρο Καστοριάς.
Ο Παύλος Μελάς αποτέλεσε υπόδειγμα γενναιότητας και αυταπάρνησης για την απελευθέρωση της πατρίδας στην ελληνική ιστορία.
Μετά το θάνατο του η δράση των Ελληνικών δυνάμεων έγινε πιο έντονη, περιορίζοντας τη δράση των Βούλγαρων κομιτατζήδων, και επιτυγχάνοντας την ένωση Δυτικής και Κεντρικής Μακεδονίας με την Ελλάδα.
Σήμερα, το όνομα του Παύλου Μελά φέρει προς τιμή του το χωριό Στάτιστα ενώ πλήθος προτομών του στολίζουν πλατείες πόλεων μεταξύ των οποίων στη Θεσσαλονίκη, την Αθήνα, την Κοζάνη και σε άλλες πόλεις της Ελλάδας. Στη Θεσσαλονίκη, μετά το πρόγραμμα Καλλικράτης, οι τρεις δήμοι "Σταυρουπόλεως, Πολίχνης, Ευκαρπίας" ενώθηκαν σε ένα δήμο με την ονομασία Παύλος Μελάς.
Ο Παύλος Μελάς θεωρείται σύμβολο του Μακεδονικού Αγώνα, και πολλά προσωπικά του αντικείμενα εκτίθενται τώρα στο Μουσείο Μακεδονικού Αγώνα Θεσσαλονίκης και στο μουσείο Παύλος Μελάς στην Καστοριά.
