Ο Παύλος Μελάς γεννήθηκε στη Μασσαλία το 1870.
Ήταν γιος του Μιχαήλ Μελά, μέλους της ομώνυμης μεγάλης και ιστορικής οικογένειας των Ιωαννίνων, και ο οποίος γεννήθηκε στη Σύρα το 1833, και πέθανε στην Αθήνα το 1897, αφού προηγουμένως υπηρέτησε την Πολιτεία, ως Βουλευτής Αττικής (εκλέγηκε το 1890) και Δήμαρχος Αθηναίων (εκλέγηκε το 1891).
Το 1886 ο Παύλος Μελάς έγινε δεκτός στη Στρατιωτική Σχολή Ευελπίδων, απ' όπου αποφοίτησε το 1890 με το βαθμό του Ανθυπολοχαγού του Πυροβολικού.
Η γνωριμία του και ο γάμος του, το 1892, με τη Ναταλία Δραγούμη, κόρη του Μακεδόνα πολιτικού Στέφανου Δραγούμη - η οικογένεια Δραγούμη καταγόταν από το Βογατσικό Καστοριάς - και αδελφή του Ίωνα Δραγούμη, ήταν καθοριστική για την μετέπειτα πορεία του Παύλου Μελά, ο οποίος είχε ανδρωθεί σ' ένα περιβάλλον με έντονο τον εθνικό παλμό, καθώς σ' αυτήν βρήκε μιαν εξαίρετη σύντροφο και συνεργάτιδα με την οποία μοιραζόταν την ίδια αγάπη για την Πατρίδα.
Η τραγική ήττα της Ελλάδας στον Ελληνοτουρκικό Πόλεμο του 1897, στον οποίο και ο ίδιος συμμετείχε, πλήγωσε βαθιά τον Παύλο Μελά. Πιστεύοντας όμως ότι η χώρα θα ξαναβρεί το δρόμο της, αντέδρασε μέσα στο κλίμα της γενικής απογοήτευσης που τότε κυριαρχούσε.
Την ίδια εποχή τα γεγονότα στη Μακεδονία προκαλούν την Ελλάδα να πάρει θέση απέναντι στις βιαιοπραγίες Τούρκων και Βούλγαρων, η οποία περιοριζόταν σε διαβήματα προς τις άσπονδες φίλες της τις Μεγάλες Δυνάμεις.
Το 1902, ο Ίων Δραγούμης διορίζεται Υποπρόξενος στο Μοναστήρι. Αμέσως κηρύσσει "Ιερή Εκστρατεία" στην ευρύτερη περιοχή. Κατηχεί και εμψυχώνει το λαό της Δυτικής Μακεδονίας και ορίζει διοικητικές επιτροπές σε πόλεις και χωριά. Ιδρύει και οργανώνει τη "Μακεδονική Άμυνα".
Το 1903, η Βουλγαρική Προπαγάνδα αποφασίζει να παρουσιάσει στην Ευρώπη το δήθεν "Μακεδονικό Ζήτημα". Στόχος η ενσωμάτωση της Μακεδονίας στο Βουλγαρικό Κράτος, όπως λίγα χρόνια πριν είχε γίνει με την Ανατολική Ρωμυλία.
Την Άνοιξη του 1903 σχηματίζεται στην Αθήνα μια επιτροπή, η "Μακεδονική Φιλική Εταιρεία" από τον Αργύριο Ζάχο, τον Θεόδωρο Μόδη και τον Θεόδωρο Καπετανόπουλο, που έχει σαν σκοπό να πειστεί η Ελληνική Κυβέρνηση να ενισχύσει την ένοπλη άμυνα των καταδυναστευόμενων από Τούρκους και Βούλγαρους, Ελλήνων στη Μακεδονία.
Στις 20 Ιουλίου 1903 λαμβάνει χώρα η Βουλγαρική ψευδοεπανάσταση του 'Ιλιντεν, με προεπιλεγμένους στόχους τα ελληνικά βλαχόφωνα χωριά Νεβέσκα - Νυμφαίο και Κρούσοβο, η οποία όμως σβήνει σαν πυροτέχνημα από την άμεση αντίδραση των Τούρκων. Όμως οι Βούλγαροι πετυχαίνουν να γεμίσει η περιοχή με τα ένοπλα βουλγαρικά σώματα, τους Κομιτατζήδες που τρομοκρατούν τους Έλληνες κατοίκους.
Στις 24 Φεβρουαρίου 1904, με διαταγή της Ελληνικής Κυβέρνησης, φθάνουν μυστικά για πρώτη φορά στη Μακεδονία, για να μελετήσουν την κατάσταση και να υποδείξουν πρακτικά μέτρα, τέσσερις Αξιωματικοί του Ελληνικού Στρατού: οι λοχαγοί Αναστάσιος Παπούλας και Αλέξανδρος Κοντούλης και οι ανθυπολοχαγοί Γεώργιος Κολοκοτρώνης και Παύλος Μελάς.
Στις 22 Μαΐου 1904, στην Αθήνα, ιδρύεται μυστικά το "Μακεδονικό Κομιτάτο" με Ιδρυτή και Πρόεδρο τον Δ. Καλαποθάκη, Διευθυντή της Εφημερίδας "Εμπρός". Ανάμεσα στα πρώτα Μέλη του Μακεδονικού Κομιτάτου και ο Παύλος Μελάς. Ώσπου όμως να πειστεί η Ελληνική Κυβέρνηση να πάρει μέτρα για την απελευθέρωση της Μακεδονίας και την υπεράσπιση του Μακεδονικού Ελληνισμού, συγκέντρωναν μόνοι χρήματα και άρχισαν τον μεγάλο τους αγώνα. Αποφασίζουν να δράσουν άμεσα οργανώνοντας ένοπλα σώματα εθελοντών τα οποία και στέλνουν στη Μακεδονία, μαζί με οπλισμό για τους Μακεδόνες, και την υπεράσπισή τους από τις εναντίον τους ληστρικές και φονικές επιθέσεις Βούλγαρων και Τούρκων.
Στις 10 Ιουλίου του ίδιου έτους, ο Παύλος Μελάς ξαναπέρασες, μόνος αυτή τη φορά, στη σκλαβωμένη Μακεδονία, στην Κοζάνη και τη Σιάτιστα, με σκοπό να συγκεντρώσει στοιχεία και να μελετήσει προσωπικά την κατάσταση, κυκλοφορώντας σαν ζωέμπορος, και φέροντας το ψευδώνυμο Πέτρος Δέδες, αναλαμβάνοντας ταυτόχρονα την οργάνωση του πρώτου ένοπλου σώματός του. Στη συνέχεια επέστρεψε στην Αθήνα και ενημέρωσε την Ελληνική Κυβέρνηση για την κατάσταση στη Μακεδονία.
Ο Παύλος Μελάς ξαναήρθε για τρίτη και τελευταία φορά στη Μακεδονία, περνώντας τα σύνορα από τη μεριά της Κοζάνης στις 18 Αυγούστου 1904. Κυκλοφορούσε με το ψευδώνυμο Μίκης Ζέζας, σύνθεση των ονομάτων των παιδιών του. Διοικούσε ένα σώμα τριανταπέντε αντρών Μακεδόνων και Ηπειρωτών, Λακώνων, Κρητικών και άλλων όμως ουσιαστικά ήταν αρχηγός όλων των αντάρτικων σωμάτων που δρούσαν στις περιφέρειες Μοναστηρίου και Καστοριάς. Ο Μακεδονικός Αγώνας έχει αρχίσει. Ένας αγώνας που παρατάθηκε ως το Καλοκαίρι του 1908, οπότε θεσπίστηκε το νέο Τουρκικό Σύνταγμα. Ένας Ευγενής Αγώνας για την Ελευθερία. Όμως συγχρόνως ένας Αγώνας σκληρός, γιατί οι εθελοντές του ελληνικού ένοπλου σώματος του Παύλου Μελά, ούτε δοκιμασμένους οδηγούς είχαν, ούτε εύκολα μπορούσαν να τροφοδοτηθούν, ενώ οι αδιάκοπες βροχές τους δυσκόλευαν ακόμα και στις μετακινήσεις τους. Εκτός αυτών οι τουρκικές αρχές είχαν πληροφορηθεί το πέρασμα από τα σύνορα αυτού του ελληνικού σώματος και το καταδίωκαν με ενισχυμένο στρατιωτικό απόσπασμα. Ο Παύλος Μελάς άρχισε αμέσως τις επιθέσεις εναντίον των Βούλγαρων Κομιτατζήδων για να ξεκαθαρίσει την περιοχή, αλλά και για να οργανώσει την τοπική άμυνα. Κέντρο των επιχειρήσεών του ήταν τα χωριά Νεγοβάνη και Λέχοβο. Όμως ο αγώνας του τερματίστηκε στις 13 Οκτωβρίου 1904, ημέρα Τετάρτη, στο χωριό Στάτιστα - το οποίο σήμερα προς τιμή του ονομάζεται Μελάς - όπου βρισκόταν εκείνη την ημέρα, όταν η συμμορία κομιτατζήδων του Μήτρου Βλάχου, τον πρόδωσε και τουρκικό στρατιωτικό απόσπασμα κύκλωσε το χωριό και το σπίτι στο οποίο βρισκόταν ο Παύλος Μελάς και τον φόνευσε, όταν έπειτα από γενναία άμυνα δύο ωρών αποφάσισε ο ίδιος και οι άνδρες του Ηρωική έξοδο. Πρώτος όρμησε ο Παύλος Μελάς που πληγώθηκε θανάσιμα όταν κάποια σφαίρα τον βρήκε στη μέση και πέθανε έπειτα από μισή ώρα. Για να μην πέσει η σωρός του Παύλου Μελά στα χέρια των Τούρκων, ο Ντίνας - ένα από τα πρωτοπαλίκαρά του - έκοψε με το σπαθί του την κεφαλή του Ήρωα, έθαψε το ακέφαλο σώμα σ' έναν πρόχειρο τάφο εκεί όπου είχε σκοτωθεί και έπειτα περνώντας μάσα από τις γραμμές του τουρκικού αποσπάσματος, έφτασε στο χωρίο Ζέλοβο, όπου σ' ένα σπίτι στην άκρη του χωριού έθαψε και την κεφαλή του Παύλου Μελά. Το ακέφαλο σώμα του Παύλου Μελά βρήκαν οι Τούρκοι και μετέφεραν στην Καστοριά. Εκεί μεταφέρθηκε αργότερα και η κεφαλή του και μαζί τάφηκαν από τον Μητροπολίτη Καστοριάς Γερμανό Καραβαγγέλη - σε αντίδραση Τούρκων και Βούλγαρων - στο Πισοδέρι Καστοριάς σε αφανή τάφο κάτω από την Αγία Τράπεζα.
Η είδηση του Ηρωικού θανάτου του Παύλου Μελά συγκλόνισε το Πανελλήνιο. Ολόκληρη η Αθήνα πένθησε για τον χαμό του Ευγενούς άνδρα, ο οποίος στάθηκε ο πρωτομάρτυρας του Αγώνα για την Απελευθέρωση και την Ένωση της Μακεδονίας με την Ελλάδα, έπειτα από πέντε αιώνες δουλείας.
Ο θάνατος του Παύλου Μελά τον έκανε Ήρωα και σύμβολο του Μακεδονικού Αγώνα και έγινε αφορμή να σπεύσουν στη Μακεδονία πολλοί Έλληνες Αξιωματικοί.
Ο Μακεδονικός Αγώνας, οργανώθηκε, απλώθηκε και γιγαντώθηκε τα επόμενα χρόνια για να καταλήξει με τους νικηφόρους Α' & Β' Βαλκανικούς Πολέμους του 1912 - 13, να πραγματοποιήσει το μεγάλο όνειρο του Ελληνικού Έθνους, την Απελευθέρωση της Μακεδονίας και την Ένωση της με την Ελλάδα.