Το χωριό βρίσκεται 10 χιλιόμετρα νοτιοδυτικά από την κεντρική πόλη της Σάμου και περιβάλλεται από χαμηλούς λόφους που το κρύβουν από τη θάλασσα. Οι Μυτιληνιοί είναι ένα από τα πιο πυκνοκατοικημένα χωριά του νησιού με περίπου 2500 μόνιμους κατοίκους. Κατά πάσα πιθανότητα πήρε το όνομά του από τους πρώτους κατοίκους που ήρθαν από τη Μυτιλήνη και εγκαταστάθηκαν στο χωριό. Το χωριό έχει ένα πολύ ενδιαφέρον παλαιοντολογικό μουσείο με πλούσια συλλογή από οστά σπάνιων ζώων που έζησαν στο νησί και ειδικότερα στην περιοχή του χωριού Μυτιληνιοί πριν από 8-10 εκατομμύρια χρόνια. Αν έχετε διαβάσει σαν παιδί το βιβλίο της Άλκης Ζέη «Το καπλάνι της βιτρίνας» θα θελήσετε να επισκεφτείτε το μουσείο και για ένα ακόμα λόγο: για να δείτε από κοντά το περίφημο καπλάνι στο οποίο αναφέρεται η συγγραφέας. Πρόκειται για ένα αιλουροειδές, το οποίο πέρασε στη Σάμο από την απέναντι ακτή της Μικράς Ασίας πριν από 150 χρόνια. Το ζώο τότε αιχμαλωτίστηκε και θανατώθηκε από τους κατοίκους του χωριού Πύργος, ταριχεύθηκε με τα μέσα της εποχής και το ταριχευμένο ζώο κατέληξε στο Μουσείο μετά από δωρεά του Δήμου Σαμίων. Μέσα στο χωριό ο επισκέπτης μπορεί να επισκεφθεί αρκετές εκκλησίες, την Παναγιά, την Αγία Ματρώνα, τον Άγιο Δημήτριο, τον Άγιο Αντώνιο, την εκκλησία του Ευαγγελισμού καθώς και το Μετόχι του Πατριαρχείου Ιεροσολύμων που είναι το πιο σημαντικό από αυτά. Σε απόσταση πέντε περίπου χιλιόμετρων νοτιοανατολικά από το χωριό μπορείτε να επισκεφτείτε το Μοναστήρι της Αγίας Τριάδας, χτισμένο το 1824.