Η Ευαγγελίστρια είναι ο ενοριακός ναός της δεύτερης μεγαλύτερης πόλης της Λήμνου, του Μούδρου, και χρονολογείται στις αρχές του 20ού αιώνα (1903). Eίναι τρίκλιτη βασιλική, με δύο καμπαναριά στην πρόσοψη, την οποία κοσμεί επίσης ένας μεγάλος ρόδακας. Για να περάσει κανείς στον προαύλιο χώρο, πρέπει να διαβεί μια λαξευτή, πέτρινη πύλη.
Η Ευαγγελίστρια Μούδρου είναι το επίκεντρο του εορτασμού του Ευαγγελισμού της Θεοτόκου σε ολόκληρη τη Λήμνο. Ο Επιτάφιος της εκκλησίας είναι δωρεά του ναύαρχου Παύλου Κουντουριώτη, αρχηγού του Γενικού Επιτελείου Ναυτικού που βρέθηκε στη Λήμνο επί Α’ Παγκοσμίου Πολέμου, ενώ τα επίσημα εγκαίνια του ναού έγιναν το 1919.
Η ιστορία που συνοδεύει το ναό όμως είναι θλιβερή και τραγική. Όπως λέγεται, πριν την Ευαγγελίστρια Μούδρου στο σημείο υπήρχε μετόχι της Αγίας Μαρίνας της μονής Κουτλουμουσίου του Αγίου Όρους. Κάποτε όμως, οι Τούρκοι κυρίαρχοι της Λήμνου ανακάλυψαν σε ένα πηγάδι πτώματα αξιωματικών και για να εκδικηθούν τις δολοφονίες κατέκαψαν την εκκλησία, καίγοντας μαζί και τους μοναχούς. Οι δύο που κατόρθωσαν να σωθούν, κατέφυγαν στο Άγιο Όρος και κατήγγειλαν πως επρόκειτο για προβοκάτσια περιοίκων που επεδίωκαν να διαλυθεί το μετόχι και να οικειοποιηθούν τα κτήματά του. Η απόφαση του ηγούμενου της Μονής Κουτλουμασίου ήταν να επιβάλει το Μούδρο σε επιτίμιο (κατάρα), το οποίο μάλιστα λύθηκε πανηγυρικά μόλις το 2001.