Ο Γρηγόριος Παπαθεόδωρος γεννήθηκε το 1770 στο χωριό Αλβάινα (Ολυμπία) από τους γονείς του Θεόδωρου Παπαθεοδώρου και της Αναστασίας. Η πρώιμη εκπαίδευσή του ξεκίνησε στο χωριό του, αλλά συνέχισε τις σπουδές του στη Μονή Βυτίνας, η οποία ήταν ευρέως γνωστή για την πλούσια και ποικιλόμορφη βιβλιοθήκη της.  Εκτός από τα ακαδημαϊκά του ενδιαφέροντα, ο Γρηγόρης είχε πάθος για τις γλώσσες. Μιλούσε άπταιστα τουρκικά, αραβικά, γαλλικά, ιταλικά και φυσικά ελληνικά. Ωστόσο, το πάθος και η κλήση του επικεντρώθηκαν γύρω από την πίστη και την κοινότητά του.

​

Σε ηλικία 30 ετών, ο Γρηγόριος αγκάλιασε ένα μονοπάτι υπηρεσίας στην Εκκλησία. Με ακλόνητη πίστη και αφοσίωση, ο Γρηγόριος ανέβηκε γρήγορα στις τάξεις της ιεροσύνης.  Το 1800 έγινε ορδαίοςαπέκτησε Διάκονο και αργότερα ανυψώθηκε στη θέση του Πρεσβύτερου και του Καγκελαρίου. Ο σημαντικός του ρόλος ως Επισκόπου Μεθώνης, Ναυαρίνου και Νεοκάστρου αποκαλύφθηκε μεταξύ 1816-25, από τον Πατριάρχη Κωνσταντινουπόλεως Κύριλλο ΣΤ'.

​

Το 1817, ο Γρηγόριος ξεκίνησε ένα κρίσιμο ταξίδι στη Ρωσία, όπου υποστήριξε ένθερμα την ελληνική ανεξαρτησία ενώπιον του τσάρου, μοιράζοντας τις οδυνηρές ιστορίες των καταπιεσμένων Ελλήνων υπό τουρκική κυριαρχία. Έχοντας λάβει επιτυχώς ρωσική υποστήριξη, ο Γρηγόριος επέστρεψε στη Μεθώνη όπου αργότερα εντάχθηκε στη Φιλική Εταιρεία (μυστικό πολιτικό και επαναστατικός οργάνωση που ιδρύθηκε το 1814 και μοναδικός σκοπός της ήταν να ανατρέψει την Τουρκοκρατία από Ελλάδα και καθιερώστε μια ανεξάρτητο Ελληνικό Κράτος).  Η αυξανόμενη φήμη, ο θαυμασμός και ο σεβασμός του τον είδαν να στρατολογεί ενεργά περισσότερους από 150 συμπατριώτες του στη Φιλική Εταιρεία. Αυτό έπαιξε καθοριστικό ρόλο στην Ελληνική Επανάσταση του 1821, οδηγώντας σε στρατιωτικές ενέργειες που είχαν ως αποτέλεσμα τις επιτυχείς πολιορκίες της Μεθώνης και του Νεοκάστρου.  Με προκλητικό στρατό οι τουρκικές δυνάμεις αναγκάστηκαν να παραδώσουν τα κλειδιά του κάστρου της Μεθώνης στον γενικό διοικητή Επίσκοπο Γρηγόριο.