Ο Παύλος Μελάς γεννήθηκε στις 29 Μαρτίου του 1870 στη Μασσαλία, όπου ο πατέρας του Μιχαήλ Μελάς (1833-1897) δραστηριοποιούταν ως έμπορος. Το 1886 εισήλθε στη Σχολή Ευελπίδων και εξήλθε ως ανθυπολοχαγός του Πυροβολικού στις 8 Αυγούστου του 1891. Τον επόμενο χρόνο νυμφεύτηκε τη Ναταλία Δραγούμη (1872-1973), κόρη του τραπεζίτη και πολιτικού Στέφανου Δραγούμη, με την οποία απέκτησε δύο παιδιά, τον στρατιωτικό Μιχαήλ Μελά (1894-1950) και τη χημικό Ζωή Μελά – Ιωαννίδη (1898-1996).
Ήταν ένας από τους αξιωματικούς που το 1894, λίγο καιρό αφότου επέδραμαν στα γραφεία της εφημερίδας Ακρόπολις, συνέστησαν την Εθνική Εταιρεία, μια αλυτρωτική οργάνωση, της οποίας ήταν δραστήριο μέλος. Ως μέλος της Εθνικής Εταιρείας συμμετείχε στη διοργάνωση της εισβολής στην Οθωμανική Αυτοκρατορία Ελλήνων ατάκτων που προκάλεσε τον ελληνοτουρκικό πόλεμο του 1897, ο οποίος έληξε με συντριπτική ήττα της Ελλάδας και βύθισε το Μιχαήλ Μελά σε θανάσιμη θλίψη.
Μετά την αυτοδιάλυση της Εθνικής Εταιρείας το 1900 αναμίχθηκε στις μακεδονικές υποθέσεις, πεδίο ελληνοβουλγαρικού ανταγωνισμού, που απασχολούσαν όλα τα μέλη της οικογένειας Δραγούμη. Σε συνεργασία με τον Ίωνα Δραγούμη στάθηκε από τους πρωτεργάτες του Μακεδονικού αγώνα, ενισχύοντας τις ελληνικές διεκδικήσεις με όπλα και άνδρες.
Η κατάσταση που επικρατούσε εκείνη την περίοδο στα Βαλκάνια, ήταν ταραγμένη. Σε περιοχές όπως η Κρήτη, η Θεσσαλία, η Μακεδονία και η Ήπειρος (που ποθούσαν να ενωθούν με την ήδη απελευθερωμένη Ελλάδα), καθώς και σε πάμπολλες άλλες περιοχές στα Βαλκάνια, ξεσπούν συνεχώς επαναστάσεις ενάντια στον Σουλτάνο.
Η Μακεδονία μάλιστα, υποφέρει τόσο από τον Τουρκικό ζυγό, όσο και από τη Βουλγαρική Εξαρχία. Η Βουλγαρική προπαγάνδα χρησιμοποιεί κάθε μέσο (κυρίως εκφοβισμούς και βία, αλλά και στυγνές δολοφονίες σε πολλές περιπτώσεις) και κάθε της ενέργεια, αποσκοπεί στον εκβουλγαρισμό του τότε πληθυσμού της Μακεδονίας. Η Ελληνική Κυβέρνηση δεν επιχειρεί τίποτε, επίσημα, μέχρι το 1904. Ακόμη και εκείνη την περίοδο, ο Παύλος Μελάς, μαζί με άτομα που μοιράζονται τις ίδιες ιδέες μ’ αυτόν, αγωνίστηκε για να αφυπνίσει υπεύθυνους και κοινή γνώμη.
Το Μάρτιο του 1904, εν μέσω όξυνσης της εθνοθρησκευτικής διαμάχης στον απόηχο της εξέγερσης του Ιλιντεν, μαζι με τους λογαχούς Αλέξανδρο Κοντούλη και Αναστάσιο Παπούλα και τον ανθυπολοχαγό Γεώργιο Κολοκοτρώνη, συμμετέχει σε μυστική αποστολή στη Μακεδονία με το ψευδώνυμο Μίκης Ζέζας (Μίκης, από το όνομα του γιου του Μιχαήλ, που τον φωνάζουν χαϊδευτικά Μίκη και Ζέζας, από το όνομα της κόρης του Ζωής, που τη φωνάζουν χαϊδευτικά Ζέζα), κατόπιν εντολής της κυβέρνησης Θεοτόκη. Η ομάδα των τεσσάρων αξιωματικών, συνοδευόμενη από μακεδόνες αγωνιστές, δραστηριοποιήθηκε στη δυτική Μακεδονία σε μυστική αποστολή η οποία κατέληξε σε αντικρουόμενα αποτελέσματα αναφορικά με τη σκοπιμότητα αποστολής ένοπλων σωμάτων από την Ελλάδα.
Τον Ιούλιο επισκέφθηκε ιδιωτικά την Κοζάνη και τη Σιάτιστα και αποφάσισε να αναλάβει αντάρτικη δράση στην περιοχή. Τον Αύγουστο ορίστηκε από το νεοϊδρυθέν Μακεδονικό Κομιτάτο αρχηγός των ελληνικών ομάδων στην περιοχή Καστοριάς και Μοναστηρίου και εισήλθε για τρίτη φορά στην οθωμανοκρατούμενη τότε περιοχή της Μακεδονίας , αυτή τη φορά επικεφαλής ένοπλου σώματος που αποτελούνταν από αρκετούς Μακεδόνες, Λάκωνες και Κρήτες, και στα μέσα Σεπτεμβρίου στρατοπέδευσε στην περιοχή της Καστοριάς.
Με τους άνδρες του περιόδευσε σε ετερόγλωσσα χωριά της περιοχής καταδιώκοντας κομιτατζήδες της ΕΜΕΟ, πειθαναγκάζοντας εξαρχικούς σλαβόφωνους να επιστρέψουν στο Πατριαρχείο και οργανώνοντας ένα δίκτυο υποστηρικτικό της δράσης των ελληνικών σωμάτων. Ενώ βρισκόταν στο χωριό Στάτιστα της Καστοριάς, επιδιώκοντας να συναντηθεί με την ανταρτοομάδα των Καούδη και Κύρου, το σώμα του δέχτηκε επίθεση από ένα απόσπασμα του οθωμανικού στρατού, που παραπλανημένο από τον κομιτατζή Μήτρο Βλάχο· ο Μελάς τραυματίστηκε από έναν πυροβολισμό και πέθανε υπό ομιχλώδεις συνθήκες. Μετά από περιπετειώδη πορεία η αποτμηθείσα κεφαλή του ενταφιάστηκε τελικά μαζί με το σώμα του στην Καστοριά, ενώ οι ακριβείς περιστάσεις του θανάτου του συσκοτίστηκαν.
Ο θάνατος του Μελα διαδόθηκε σὰν αστραπὴ στὴν Αθήνα. Αν και λίγοι γνώριζαν πὼς βρισκόταν στὴ Μακεδονία, ολοι τὸν εκλαψαν. Τὸ τέλος του ηταν εκείνο που ο ίδιος στὰ γραμματά του αφηνε νὰ διαφανεί. Είχε τὸ νόημα τής θυσίας, συντάραξε ὁλόκληρο τὸ Εθνος καὶ παρακίνησε πολλοὺς συναδέλφους του αξιωματικοὺς νὰ βγούν με σώματα στὴ Μακεδονία γιὰ νὰ εκδικηθούν τὸ θάνατό του. Ἐνώ ώς τότε η υπόθεση τής Μακεδονίας ήταν υπόθεση μικρού αριθμού Ελλήνων, απὸ τὸ θάνατο του Μελά έγινε υπόθεση ολόκληρου του ελληνισμού Ἡ θυσία του είχε πετύχει ό,τι καμιὰ άλλη δύναμη δὲν είχε κατορθώσει καὶ έδειξε στὸν κόσμο ολόκληρο πὼς ο ελληνισμὸς έξω απὸ τὰ όρια του μικρού βασιλείου δὲν είχε χαθεί.
Στην Ελλάδα τιμάται ως ήρωας, συνδεδεμένος με τον Μακεδονικό αγώνα.
Η θυσία του σηματοδότησε την ουσιαστική έναρξη του Μακεδονικού Αγώνα, που κορυφώθηκε με τους Βαλκανικούς Πολέμους του 1912-1913.
