Η Νέα Κούταλη χτίστηκε το 1926 στη θέση Αγία Μαρίνα, στη μεσημβρινή πλαγιά του λόφου Στρομπόλιθος, για να εγκατασταθούν οι πρόσφυγες από την Κούταλη της Προποντίδας. Μαζί με τον Άγιο Δημήτριο, η Νέα Κούταλη αποτελεί το δεύτερο χωριό της Λήμνου που χτίστηκε από τους πρόσφυγες της Μικράς Ασίας.
Η Νέα Κούταλη, που ξεχωρίζει για την καλή ρυμοτομία της, είναι χτισμένη αμφιθεατρικά στον κόλπο του Μούδρου. Απλώνεται από το πευκόδασος της Αγίας Τριάδας, που φύτεψαν οι πρόσφυγες και καταλήγει στο γραφικό πετρόχτιστο λιμανάκι, το γεμάτο με ψαράδικες βάρκες και καΐκια. Η Νέα Κούταλη είναι φημισμένη σε Ελλάδα και εξωτερικό για τους σφουγγαράδες της. Την 1η Ιουλίου του 2006 εγκαινιάστηκε το “Μουσείο Ναυτικής Παράδοσης και Σπογγαλιείας”.
Παγκόσμια γνωστή έκανε την Κούταλη, ο Παναγής Κουταλιανός, φημισμένος παλαιστής και αρσιβαρίστας κατά την δεκαετία 1882-1892. Ήταν χειροδύναμος ναυτικός και έγινε γνωστός στις ΗΠΑ, όταν κατανίκησε πολλούς γνωστούς παλαιστές της εποχής. Πάλεψε και στραγγάλισε μία άγρια τίγρη, της οποίας το δέρμα φορούσε στους αγώνες και έκανε επιδείξεις δύναμης λυγίζοντας σίδερα, σπάζοντας βράχους και αλυσίδες σε όλο τον κόσμο.