Γεννήθηκε στο χωριό Παράκοιλα της Λέσβου στις 6 Ιουλίου 1876 με το όνομα Ευστράτιος Αγριτέλης (ή Αγριτέλλης). Σε ηλικία 9 ετών οι γονείς του τον αφιέρωσαν στη Μονή Λειμώνος κοντά στην Καλλονή, όπου ο ηγούμενος αρχιμανδρίτης Άνθιμος Γεωργιέλλης του έδωσε το όνομα Ευθύμιος.
Το 1889 γράφτηκε στη Λειμωνιάδα Σχολή της μονής, όπου έλαβε εγκύκλιες σπουδές ως το 1892. Το 1900 αναχώρησε με υποτροφία της μονής Λειμώνος για την Κωνσταντινούπολη, όπου σπούδασε στη Θεολογική Σχολή της Χάλκης και χειροτονήθηκε διάκονος. Μετά την αποφοίτησή του διορίστηκε διευθυντής της Λειμωνιάδας Σχολής και ιεροκήρυκας της επαρχίας Μήθυμνας.
Το 1910 χειροτονήθηκε πρεσβύτερος και διατέλεσε ως το 1912 πρωτοσύγκελος Μήθυμνας. Στις 27 Ιουλίου 1912, και αφού στο μεταξύ είχε προσληφθεί ως γενικός αρχιερατικός επίτροπος του μητροπολίτη Αμάσειας Γερμανού Καραβαγγέλη, χειροτονήθηκε επίσκοπος Ζήλων στον δυτικό Πόντο.
Ενάρετος και δραστήριος, κυβέρνησε με ένθερμο ζήλο και πατριωτισμό τη μεγάλη μητρόπολη της Αμάσειας. Στα δέκα χρόνια της αρχιερατείας του παρουσίασε πραγματικά πληθωρικό έργο.
Οι συνθήκες διαβίωσης του ελληνισμού του Πόντου την εποχή εκείνη ήταν εξαιρετικά τραγικές, εξαιτίας των σκληρών και φανατικών διωγμών των Τούρκων. Με την παρουσία του όμως αφύπνιζε και τόνωνε το εθνικό και θρησκευτικό συναίσθημα των κατοίκων της περιοχής.
Με το ξέσπασμα του Α’ Παγκόσμιου Πολέμου ο Τούρκος Εμβέρ Πασάς έδωσε εντολή κατάταξης σε όλους τους Οθωμανούς πολίτες για πόλεμο κατά των Ρώσων. Πολλοί Παφραίοι, με προτροπή του Ευθύμιου, αρνήθηκαν να καταταγούν στον τουρκικό στρατό και βγήκαν στα βουνά, όπου δημιούργησαν αντάρτικα ένοπλα τμήματα.
Οι Τούρκοι τους κατεδίωκαν σαν λιποτάκτες, ιδιαίτερα στην περιοχή της Πάφρας και της Σαμψούντας. Ο Ευθύμιος οδοιπορούσε αδιάκοπα από ενορία σε ενορία, συχνά υπό καταδίωξη και κίνδυνο σύλληψης, χωρίς να λογαριάζει πείνα, αρρώστιες και κακουχίες, για να βοηθήσει, να εμψυχώσει και να στηρίξει τους Έλληνες.
Οι Τούρκοι για λόγους στρατηγικούς είχαν αποφασίσει την εκτόπιση των χριστιανικών πληθυσμών Αρμενίων και Ελλήνων του παραθαλάσσιου Πόντου στο εσωτερικό της Ανατολής. Οι διωγμοί ήταν στην ημερήσια διάταξη, και ο Ευθύμιος ήταν υποχρεωμένος –καθώς ο μητροπολίτης Γερμανός απουσίαζε συχνά– να φροντίζει και να διευθετεί όλες τις υποθέσεις των χριστιανών.
Είχε πολιτική ευστροφία. Ήταν ο νους και η ψυχή των αντάρτικών ομάδων του Νεπιέν Νταγ και κατ’ επέκταση όλων των ανταρτικών σωμάτων του Ταφσάν Νταγ, Αγιού Τεπέ κτλ., που είχαν ιδρυθεί από τον Καραβαγγέλη και ο αριθμός τους ανέρχονταν στους περίπου 20.000 αντάρτες.
Το 1917 ανέλαβε ηγετικό ρόλο σε ένοπλες ομάδες ανταρτών, κατευθύνοντάς τες κατά του τουρκικού στρατού και των τσετών, που δρούσαν ως μισθοφόροι των Τούρκων κατά των Ελλήνων.
Στις 15 Αυγούστου 1919 συγκέντρωσε 12.000 αντάρτες έξω από την κωμόπολη Τσασούρ, νότια της Πάφρας, με επικεφαλής τον οπλαρχηγό Κυριάκο Παπαδόπουλο (παππού του Κοτζά Αναστάς), με αποτέλεσμα την ολοσχερή καταστροφή της πόλης και τον αφανισμό των Τούρκων ενόπλων. Από εκείνη τη μέρα οι Τούρκοι τον καταζητούσαν ζωντανό ή νεκρό, θεωρώντας τον αρχηγό των ανταρτών του δυτικού Πόντου.
Στις 21 Ιανουαρίου 1921 συνελήφθη με πολλούς άλλους προκρίτους της Αμάσειας και φυλακίστηκε . Στη φυλακή της Σούγιας υπέφερε φρικτά βασανιστήρια, και εξαντλημένος από τις κακουχίες και τις στερήσεις πέθανε στις 29 Μαΐου του 1921.
Οι φύλακες πέταξαν στα σκουπίδια το σώμα του, το οποίο πιστοί περιμάζεψαν και έθαψαν κρυφά στο προαύλιο της Αγίας Τριάδας. Οι άλλοι συγκρατούμενοί του –μεταξύ των οποίων και ο Πλάτων Αϊβαζίδης–, συνολικά 174, καταδικάστηκαν σε θάνατο και απαγχονίστηκαν στις 21/9/1921 στην πλατεία της Αμάσειας.
Η αγιοκατάταξή του έγινε το 1992 μαζί με τους μάρτυρες Χρυσόστομο Σμύρνης, Προκόπιο Ικονίου, Γρηγόριο Κυδωνιών, Αμβρόσιο Μοσχονησίων και των συν αυτοίς Μικρασιατών νεομαρτύρων. Η μνήμη τους τιμάται τον Σεπτέμβριο, την Κυριακή προ της Υψώσεως του Σταυρού.
