Στις 12 Φεβρουαρίου του 1897 o Μελάς υπηρετούσε ως αρχιφύλακας στο Πανεπιστήμιο Αθηνών όταν τον κάλεσαν να επιστρέψει με τους άνδρες του στο στρατώνα του πυροβολικού. Υπό την πίεση της Εθνικής Εταιρείας και ενάντια στη θέληση των Μεγάλων Δυνάμεων, η ελληνική κυβέρνηση είχε αποφασίσει να στείλει εκστρατευτικό σώμα στην Κρήτη για τη στήριξη της εκεί επανάστασης. Ο Μελάς απογοητευμένος έμαθε πως η μονάδα του δεν περιλαμβανόταν στο εκστρατευτικό σώμα. Την επόμενη μέρα όμως ανακοινώθηκε πως η πεδινή πυροβολαρχία του, υπό τη διοίκηση του πρίγκιπα Νικολάου, θα μετέβαινε στη Λάρισα. Στις 16 Φεβρουαρίου η μονάδα αναχώρησε με πλοίο από τον Πειραιά και μέσω Χαλκίδας και με το σιδηρόδρομο από το Βόλο έφτασε στη Λάρισα. Η αποτυχημένη εισβολή Ελλήνων ατάκτων στη Μακεδονία, οργανωμένων από την Εθνική Εταιρεία, στις 9 Απριλίου έδωσε στην οθωμανική κυβέρνηση την αφορμή που αναζητούσε για την κήρυξη πολέμου.

Στις 18 Απριλίου έγινε η διακοπή των διπλωματικών σχέσεων των δύο χωρών και η κήρυξη του πολέμου. Ο Μελάς στα ημερολόγια του εμφανίζεται ενθουσιασμένος από την έναρξη των εχθροπραξιών, όμως η γρήγορη αρνητική τροπή των πραγμάτων, η άτακτη υποχώρηση του ελληνικού στρατού και η εκκένωση της Λάρισας τον απογοήτευσαν. Στις 18 Μαΐου με την είδηση της ανακωχής από τηλεγράφημα του πατέρα του αρρώστησε με υψηλό πυρετό και ο γιατρός τον έστειλε στη Λαμία και στη συνέχεια στο πλωτό νοσοκομείο Θεσσαλία όπου υπηρετούσε ως εθελόντρια νοσοκόμα η σύζυγος του Ναταλία. Μαζί επέστρεψαν στο οικογενειακό του σπίτι στην Αθήνα όπου ανάρρωσε για μία εβδομάδα και στη συνέχεια ζήτησε και επέστρεψε στη Λαμία. Θα επέστρεφε σύντομα ξανά στην Αθήνα λόγω της ασθένειας του πατέρα του, ο οποίος πέθανε στις 17 Ιουνίου.

Εμπλοκή με το Μακεδονικό Κομιτάτο

Έχοντας τύψεις για την έκβαση του πολέμου του 1897, συμμετείχε από τους πρώτους στο ιδρυθέν το 1900, Μακεδονικό Κομιτάτο για την προώθηση της ελληνικής επιρροής στην περιοχή της Μακεδονίας, ως αντίδραση στη δράση των Βούλγαρων κομιτατζήδων. Έτσι από τον Φεβρουάριο του 1904 ο Παύλος Μελάς έσπευσε με άλλους τρεις αξιωματικούς, τους Α. Κοντούλη, Α. Παπούλα και Γ. Κολοκοτρώνη, προς επιτόπια μελέτη της κατάστασης. Αποτυγχάνοντας σε εκείνη την πρώτη προσπάθεια, επανήλθε τον Ιούλιο του ίδιου έτους οπότε και εισήλθε στη Μακεδονία ως ζωέμπορος με το όνομα «Πέτρος Δέδες». Μετά από 20ήμερη παραμονή συναντήθηκε με τον Έλληνα πρόξενο, Λάμπρο Κορομηλά, στη Θεσσαλονίκη ανταλλάσσοντας σκέψεις για ανάληψη επιχειρήσεων και στη συνέχεια επέστρεψε στην Αθήνα. Ύστερα από παρέμβαση της ελληνικής κυβέρνησης ο Μελάς ανέλαβε την αρχηγία του Μακεδονικού αγώνα ενάντια στους Βούλγαρους με την εντολή να ασκεί καθήκοντα αρχηγού και στις μικρότερες ομάδες που δρούσαν εν τω μεταξύ στις περιφέρειες Μοναστηρίου και Καστοριάς.

Μακεδονική δράση

Τη νύχτα της 27ης με 28ης Αυγούστου ο Παύλος Μελάς με το επιχειρησιακό όνομα «Καπετάν Μίκης Ζέζας», με ένοπλο σώμα 35 ανδρών, που το αποτελούσαν Μακεδόνες, Μανιάτες και Κρητικοί, διέβη τα ελληνοοθωμανικά σύνορα και εισέβαλε στα εδάφη της Μακεδονίας, κοντά στο Όστροβο (σημερινή Άρνισσα). Στις 30 Αυγούστου ο ληστής Θανάσης Βάγιας, τον οποίο ο Μελάς είχε προσλάβει ως οδηγό, λιποτάκτησε και στη συνέχεια κατέδωσε το σώμα του Μελά στους Οθωμανούς. Τις επόμενες μέρες, το σώμα του Μελά περιπλανήθηκε στην περιοχή της Σαμαρίνας, με τον ασυνήθιστο σε κακουχίες Μελά να καταπονείται ιδιαίτερα. Στις 5 Σεπτεμβρίου, ύστερα από πορεία πολλών ημερών όπου αντιμετώπισαν την καχυποψία του τοπικού πληθυσμού, ο Μελάς και οι σύντροφοι του έφθασαν στο χωριό Ζάνσκο όπου τους βοήθησε και εφοδίασε πρόσωπο της εμπιστοσύνης τους.

Στις 15 Σεπτεμβρίου ο Μελάς πραγματοποίησε την πρώτη του επιχείρηση. Συνέλαβε έξω από το Σρέμπερνο έναν ηλικιωμένο και δύο παιδιά 8 και 15 ετών και στην συνέχεια τον καταζητούμενο πατέρα του 15χρονου. Νωρίς το βράδυ, το σώμα εισέβαλε στο χωριό και συνέλαβε ακόμα έναν καταζητούμενο εξαρχικό. Αποφάσισε τελικά να μην σκοτώσει τους δύο καταζητούμενους υπό τον όρο πως θα πήγαιναν στην ελληνική Μητρόπολη και θα δήλωναν υποταγή στον εκεί Μητροπολίτη. Στις 17 Σεπτεμβρίου προσπάθησε να οργανώσει επίθεση στο χωριό Άιτος καθώς ήταν κέντρο εξαρχικών αυτονομιστών, όμως η απροθυμία συνεργασίας του ντόπιου συνεργάτη του τού άλλαξε τα σχέδια και αποφάσισε να επιτεθεί στο γειτονικό χωριό Πρεκοπάνα (σημερινή Περικοπή). Εκεί περικύκλωσε τον τοπικό πληθυσμό που εκείνη την ώρα παρακολουθούσε μια κηδεία κι απαίτησε να δηλώσουν πίστη στον Έλληνα Μητροπολίτη και να ζητήσουν την αποστολή ιερέα και δασκάλου. Για να γίνει πιστευτή η απειλή του πήρε μαζί του τον εξαρχικό δάσκαλο και τον εξαρχικό παπά, τους οποίους οι συνεργάτες του εκτέλεσαν λίγο έξω από το χωριό. Η δολοφονία φαίνεται να συγκλόνισε τον Μελά.

Στη συνέχεια κατευθύνθηκε στο χωριό Μπελκαμένη όπου τους υποδέχτηκαν μυστικά Έλληνες του χωριού. Το απόγευμα της επόμενης μέρας το σώμα μπήκε στο χωριό και υποχρέωσε τον Ρουμάνο δάσκαλο σε φυγή. Νωρίς το βράδυ, το σώμα κατευθύνθηκε για να χτυπήσει το σλαβόφωνο χωριό Νερέτ (σημερινός Πολυπόταμος). Την επόμενη μέρα όμως, τα σχέδια τους ανατράπηκαν, όταν συνειδητοποίησαν πως στο χωριό βρισκόταν σημαντική δύναμη του οθωμανικού στρατού. Κατά τη διάρκεια της άτακτης φυγής, τραυματίστηκε θανάσιμα ο συνεργάτης του Μελά, Θανάσης Καπετανόπουλος. Ο Μελάς τον σκέπασε με την κάπα του, στην οποία είχε αφήσει από αμέλεια ένα γράμμα του Καπετανόπουλου προς τον Δημήτριο Καλλέργη, τον Έλληνα πρόξενο στο Μοναστήρι. Η εύρεση της επιστολής θα οδηγούσε αργότερα σε διάβημα της Υψηλής Πύλης προς την ελληνική κυβέρνηση και την ανάκληση του Καλλέργη. Ύστερα από το επεισόδιο αυτό, το σώμα του Μελά κράτησε χαμηλό προφίλ και για αρκετές μέρες έμεινε στη Νεγοβάνη (σημερινό Φλάμπουρο).

Ο μυστηριώδης θάνατός του

Στις 12 Οκτωβρίου, ύστερα από αποτυχημένη επιδρομή στο Νερέτ, ο Μελάς και η ομάδα του κατευθύνθηκαν στα Στάτιστα (σημερινός Μελάς), ένα χωριό που τότε ήταν πλειοψηφικά σλαβόφωνο. Στο χωριό, ο ντόπιος συνεργάτης του Μελά, Ντίνας Στεργίου, μοίρασε τους άνδρες της ομάδας σε πέντε σπίτια. Στο χωριό όμως, υπήρχε οργανωμένος βουλγαρικός πυρήνας, μέλος του οποίου ειδοποίησε τον οθωμανικό στρατό για την παρουσία του ελληνικού σώματος. Στις 13 Οκτωβρίου το χωριό περικυκλώθηκε από οθωμανικό απόσπασμα 150 ανδρών και ξεκίνησαν αψιμαχίες. Το ξημέρωμα της επόμενης ημέρας, θα έβρισκε τον Μελά νεκρό υπό αδιευκρίνιστες συνθήκες.

Για τις ακριβείς συνθήκες του θανάτου του Μελά υπάρχει πλήθος εκδοχών. Κάποια στιγμή το οθωμανικό απόσπασμα εντόπισε ένα από τα κρυσφύγετα των Ελλήνων και ξέσπασαν πυροβολισμοί. Οι περισσότερες αφηγήσεις συντρόφων του Μελά αμφισβητούν το ότι υπήρξε σημαντική μάχη και είναι αμφίβολο αν ο Μελάς και όσοι ήταν μαζί του συμμετείχαν. Όλες οι εκδοχές συγκλίνουν πως κάποια στιγμή τη νύχτα ο Μελάς προσπάθησε να διαφύγει, όμως τραυματίστηκε θανάσιμα. Οι μαρτυρίες ποικίλουν για το αν ο Μελάς ύστερα από τον τραυματισμό του απεβίωσε, αυτοκτόνησε, ζήτησε από τον Ντίνα να τον αποτελειώσει ή ο τελευταίος τον σκότωσε αυτόβουλα. Φαίνεται να ήταν ο μοναδικός νεκρός της ελληνικής πλευράς. Σύμφωνα με μια αφήγηση των συμβάντων που διαδόθηκε από τις εφημερίδες της εποχής, πέθανε στα χέρια του φίλου του, Γεώργιου Στρατινάκη και η τελευταία του φράση πριν ξεψυχήσει ήταν «Βούλγαρος να μη μείνει». Ωστόσο, η εκδοχή αυτή δεν επιβεβαιώνεται από καμία μαρτυρία.

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

Στο μεταξύ όμως, ο θάνατος του Μελά είχε μαθευτεί στην Αθήνα και η εκεί οθωμανική πρεσβεία ειδοποίησε τις αρχές της Θεσσαλονίκης να βρουν το πτώμα ώστε να το χρησιμοποιήσουν σαν απόδειξη της ελληνικής επέμβασης σε οθωμανική επικράτεια. Έτσι, ενώ ο Ντίνας έκανε την εκταφή, εμφανίστηκε οθωμανικός στρατός. Τότε, έκοψε βιαστικά το κεφάλι του νεκρού και έφυγε. Το κεφάλι τάφηκε μπροστά στην Ωραία Πύλη του Ναού της Αγίας Παρασκευής στο χωριό Πισοδέρι, ενώ οι Οθωμανοί πήραν το ακέφαλο σώμα και το πήγαν στην Καστοριά για αναγνώριση. Ο Γερμανός Καραβαγγέλης, που γνώριζε τα πάντα, κινητοποίησε τη νεολαία της Καστοριάς που περικύκλωσε το Διοικητήριο και απαιτούσε να τους δοθεί το σώμα «κάποιου Ζέζα» που ήταν Έλληνας. Ο Μητροπολίτης, προειδοποιώντας ότι μπορεί να συμβούν ταραχές που θα έβλαπταν την ειρηνική συμβίωση Τούρκων και Ελλήνων κατάφερε να του δοθεί το σώμα το οποίο και τάφηκε στο παρεκκλήσιο των Ταξιαρχών κοντά στο Μητροπολιτικό Μέγαρο Καστοριάς.

Ο θάνατος του Μελά, γόνου μιας από τις σημαντικότερες ελληνικές οικογένειες, πήρε μεγάλη δημοσιότητα και συγκλόνισε την κοινή γνώμη της εποχής. Υπό την πίεση των γεγονότων η ελληνική κυβέρνηση ωθήθηκε να συμμετάσχει πιο ενεργά στον μακεδονικό αγώνα ενώ αυξήθηκε σημαντικά ο αριθμός των εθελοντών.

Υστεροφημία

Ο Παύλος Μελάς, παρά τη μικρή του συμβολή στο στρατιωτικό σκέλος των ελληνικών επιχειρήσεων στη Μακεδονία, χάρη στη στάση του και την εκτεταμένη δημοσιότητα που απέκτησε ο θάνατός του, αποτέλεσε υπόδειγμα γενναιότητας και αυταπάρνησης για την απελευθέρωση της πατρίδας στην ελληνική ιστορία. Στην Ελλάδα θεωρείται σύμβολο του Μακεδονικού Αγώνα, και πολλά προσωπικά του αντικείμενα εκτίθενται τώρα στο Μουσείο Μακεδονικού Αγώνα Θεσσαλονίκης και στο μουσείο «Παύλος Μελάς» στην Καστοριά.

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