Η ονομασία Λεμεσός, που επεκράτησε, απαντάται ήδη από τα Μεσαιωνικά χρόνια. Μεσαιωνικοί χρονογράφοι όπως ο Λεόντιος Μαχαιράς και ο Γεώργιος Βουστρώνιος, αναφέρουν την πόλη με τη σημερινή της ονομασία:... καί ἦρτεν εἰς τήν Κύπρον καί ἐπέζευσεν πρός τήν Λεμεσόν... γράφει ο Μαχαιράς διηγούμενος την επίσκεψη της αγίας Ελένης. Κι ο Βουστρώνιος σημειώνει:... καί ἔφερέν τους ὀμπρός του ὁ ‘πίσκοπος τῆς Λεμεσοῦ...
Αλλού πάλι ο Λεόντιος Μαχαιράς, μνημονεύοντας τους Ορθόδοξους επισκόπους της Κύπρου, γράφει: ...καί Τυχικοῦ τοῦ ἁγιωτάτου ἐπισκόπου Νέας Πόλεως Λεμεσοῦ. Και πράγματι, προγενέστερα η πόλη — διάδοχος της Αμαθούντος — αναφέρεται ως νέα πόλις - Νεάπολις. Είναι δε χαρακτηριστικό το γεγονός ότι και η περιοχή Αμαθούντος ονομαζόταν και ονομάζεται από τους Λεμεσιανούς Παλιά Λεμεσός.
Αλλά σε παλαιές πηγές η πόλη απαντάται και με τις ονομασίες Νέμεσος ή Νεμεσός (απ' όπου προφανώς προήλθε ο τύπος Λεμεσός) και Θεοδοσιάς ή Θεοδοσιανή.
Παρεφθαρμένοι τύποι του ονόματος Νέμεσος απαντώνται σε κείμενα ξένων ταξιδιωτών, όπως Νιμόσια (L. V. Suchen, 1336-1341), Νιμόνια (F. Faber, 1483) κλπ.
Η κυπριακή πόλη Θεοδοσιανή* αναφέρεται ως έδρα επισκόπου στα πρακτικά της Δ' Οικουμενικής Συνόδου της Χαλκηδόνος, το 451 μ.Χ., της οποίας ο τότε επίσκοπος Σωτήρ* είχε πάρει μέρος στη σύνοδο, εκπροσωπώντας μάλιστα και δυο άλλους Κυπρίους ιεράρχες, τον Ηλιόδωρον Αμαθούντος και τον Προέχιον Αρσινόης. Λίγο αργότερα η πόλη αναφέρεται ως Θεοδοσιάς (7ος μ.Χ. αιώνας) στον Βίο του αγίου Σπυρίδωνος που έγραψε ο επίσκοπος Πάφου Θεόδωρος. Κι ακριβώς από το κείμενο του Θεοδώρου Πάφου έχουμε την μαρτυρία ότι η Θεοδοσιάς ήταν η Λεμεσός ۬ ο επίσκοπος Θεόδωρος, μιλώντας για τον διατελέσαντα επίσκοπο Θεοδοσιάδος Ιωάννη*, σημειώνει ότι ο τελευταίος είχε γίνει επίσκοπος Θεοδοσιάδος, ἥτοι Νέας πόλεως τής Κυπρίων [βυζαντινής] ἐπαρχίας. Συνεπώς η Θεοδοσιάς ήταν η Νεάπολις, δηλαδή η Λεμεσός, όπως εξάλλου διευκρινίζει κι ο Λεόντιος Μαχαιράς: ...ἐπισκόπου Νέας Πόλεως Λεμεσού.
Ως Νεάπολις (=νέα πόλις, για να ξεχωρίζει από την αρχαιότερη της Αμαθούντα) η Λεμεσός απαντάται στον Βίο του αγίου Αυξιβίου. Αναφέρεται στον Bίo ότι ο απόστολος Παύλος προκειμένου να ενισχύσει με ικανό ανθρώπινο δυναμικό την μόλις ιδρυθείσα Κυπριακή Εκκλησία έστειλε στην Κύπρο μερικούς άξιους Χριστιανούς για να αναλάβουν επισκοπικές έδρες, μεταξύ δε αυτών τον Τυχικόν* με εντολή προς τον άγιο Ηρακλείδιο να τον καταστήσει επίσκοπον ἐν Νεαπόλει. Εάν δώσουμε βαρύτητα στην αναφορά αυτή του Βίου, θα πρέπει να θεωρήσουμε ότι κατά τα μέσα του 1ου μ.Χ. αιώνα η Νεάπολις - Λεμεσός δεν ήταν μικρός κι ασήμαντος οικισμός αλλά πόλη ικανή ν' αποτελέσει επισκοπική έδρα, πιθανώτατα όμως υπό τη μητρόπολη Αμαθούντος.
Η ονομασία Νέμεσος αναφέρεται για πρώτη φορά τον 10ο αιώνα (Βυζαντινοί χρόνοι), από τον Κωνσταντίνο Πορφυρογέννητο στο έργο του Περί Θεμάτων, στο οποίο και κατονομάζει 15 πόλεις ανήκουσες στο θέμα ΙΕ' [=15η περιφέρεια της αυτοκρατορίας], τό καλούμενον ἐπαρχία Κύπρου. Η Άννα Κομνηνή, στο έργο της Ἀλεξιάς, αναφέρει την πόλη ως Νεμεσός, με τον τόνο στη λήγουσα, ή ως Λεμεσός (σε κώδικα της Ἀλεξιάδος του 1641). Στο Συναξάριον πάλι του αγίου Ρηγίνου, σημειώνεται: ...εἰς τά μέρη τῆς Νεαπόλεως Νεμεσοῦ... Ο Λεόντιος Μαχαιράς πάλι (15ος αιώνας), αν και αναφέρει επανειλημμένα την πόλη ως Λεμεσόν, γράφει και τον τύπο Νεμεσός, λέγοντας: ...Θωρώντα ὁ μάστρος τοῦ Σπιταλλίου [=των Ιωαννιτών ιπποτών], ὅπου ἦτον εἰς τή Νεμεσόν...
Ποια όμως η προέλευση των ονομασιών Νέμεσος - Νεμεσός - Λεμεσός; (αφήνουμε τους τύπους Λεμησσός, Λιμησσός και τους παρόμοιους που αποτελούν νεότερους λογιοτατισμούς χωρίς σημασία۬ ο Αθ. Σακελλάριος, για παράδειγμα, γράφει ότι μερικοί διαστρέβλωσαν την ονομασία της πόλης σε ...Λιμησό για να δικαιολογήσουν ετυμολογία της από τη λέξη λιμήν, όπως ο Γερμανός W.H. Engel στο βιβλίο του Kypros, Βερολίνο, 1841).
Μερικοί υποστήριξαν ότι η ονομασία Λεμεσός προέρχεται από την ονομασία Αμαθούς, μαζί με το γαλλικό άρθρο La (L' Amathus, Lamasous, Λεμεσός). Άλλοι ετυμολογούν την ονομασία από το ...Νέα Τελμησσός (Σάθας), αλλά δεν μαρτυρείται στην Κύπρο αρχαία πόλη Τελμησσός. Ο αρχιμανδρίτης Κυπριανός θεωρεί ότι η ονομασία προήλθε από το Λιμόσινο, λεγομένην ἐκ μιας ἐπαρχίας τῆς Φράντζας, προσθέτοντας ὅτι ἦτον πῶτον ἐκεί ἕνα μέγα δάσος ἐκ τοῦ ὁποίου τό πρότερον ἐκράζετο Νέμεσος. Ο Κυπριανός ονομάζει Νέμεσος κάποιο δάσος που υπήρχε στην περιοχή, έχοντας πιθανότατα υπόψη το λατινικό nemus (=δάσος), όπως εικάζει ο Σίμος Μενάρδος. Ο Μενάρδος δημοσίευσε ολόκληρη πραγματεία για τις ονομασίες της πόλης, με τίτλο Λεμεσός (εφημερίδα Άλήθεια Λεμεσού, 21.2.1903 και αναδημοσίευση στο Τοπωνυμικαί καί Λαογραφικαί Μελέται, Λευκωσία, 1970, σσ. 106-112). Ο ίδιος, στο Τοπωνυμικόν τῆς Κύπρου, προτείνει ότι τό Νεμεσός σχετίζεται πιθανῶς πρός τήν Νέμεσιν, ἧς πρώτη μνεία ὡς θεᾶς γίνεται ἐν τοῖς Κυπρίοις.
Πράγματι έχουν βρεθεί στη Σαλαμίνα επιγραφές σχετικές προς την Νέμεσιν*, δεν μαρτυρείται όμως ύπαρξη ναού ή λατρεία της στην περιοχή της Λεμεσού από τα μέχρι τώρα ανασκαφικά δεδομένα.
Διαστρεβλωμένη η ονομασία Νέμεσος κατά διάφορους τρόπους, απαντάται και σε έγγραφα της περιόδου της Φραγκοκρατίας και σε κείμενα, αναφερόμενη κυρίως ως έδρα Λατίνων επισκόπων. Μερικοί πάλι θεωρούν το Νέμεσος ως ονομασία αραβικής προελεύσεως. Νομίζουμε πως δεν χωρεί αμφιβολία ότι η ονομασία Λεμεσός αποτελεί νεότερο τύπο της ονομασίας Νεμεσός - Νέμεσος. Για το Νέμεσος, ενδιαφέρουσα πρόταση έκαμε ο Κ. Χατζηιωάννου (ΑΚΕΠ , Ε', 1983, αρ. 201):
Υποστηρίζουμε, γράφει, ότι ο αρχικός τύπος ήταν αυτός του Πορφυρογέννητου «Νέμεσος»... και ότι προήλθε από το επίθετο «ανάμεσος», εννοείται πόλις, επειδή ήταν νέα πόλις ανάμεσα στις δυο αρχαίες, την Αμαθούντα και το Κούριον. Γι' αυτό και λέγεται στην αρχή περιφραστικά το όνομα της «Νεαπόλεως Νεμεσού», δηλαδή της Νέας πόλεως της «αναμέσου» Αμαθούντος και Κουρίου ...«Αναμέσους» πόλεις αναφέρει και ο Ηρόδοτος...
Ο τύπος Ανάμεσος μετατράπηκε σε Ανέμεσος, απ' όπου Νέμεσος και Νεμεσός, για να καταλήξει στον τύπο Λεμεσός που επεκράτησε. Αναφέρεται ότι η περιοχή της αρχαίας Αμαθούντος ονομαζόταν και ονομάζεται από τους Λεμεσιανούς «Παλιά Λεμεσός». Προστίθεται εδώ ότι τούτο ευρίσκεται σημειωμένο και σε πολλούς παλαιούς χάρτες (16ου αιώνα κ.ε.), όπου η Αμαθούς ευρίσκεται σημειωμένη ως Limisa Vechio, δηλαδή ακριβώς «Παλιά Λεμεσός». Έτσι επίσης αναφέρεται μερικές φορές η Αμαθούς και σε κείμενα ξένων επισκεπτών της Κύπρου, διαφόρων εποχών.
Η άποψη του αρχιμανδρίτη Κυπριανού (1788) ότι προήλθε η ονομασία αυτή «από το Λιμόσινο, λεγομένην εκ μιας επαρχίας της Φράντζας», δεν φαίνεται να ευσταθεί. Στην Γαλλία υφίστατο, πράγματι, μία πόλη που κατά την Αρχαιότητα ονομαζόταν Νεμεσός, η σημερινή Κλερμόν-Φεράν. Το δε «Λιμόσινο» είναι το διαμέρισμα Λιμουζέν (Limousin) με πρωτεύουσα του την πόλη Λιμόζ (Limoges). Μπορεί μεν αυτά τα ονόματα να έχουν κάποια ομοιότητα με εκείνο της Λεμεσού ή και με το προγενέστερο Νέμεσος, δεδομένου όμως ότι το Νέμεσος της Κύπρου μνημονεύεται ήδη από τον 10ο αιώνα (από τον Κωνσταντίνο Πορφυρογέννητο), δεν βλέπουμε με ποιον τρόπο θα ήταν δυνατό τότε (Βυζαντινοί Χρόνοι) η Κύπρος να είχε τέτοιες σχέσεις με τη Γαλλία, ώστε να «δανειζόταν» από εκεί ονόματα για δικούς της οικισμούς.
Η άποψη του Κ. Χατζηϊωάννου (ΑΚΕΠ , Ε', 1983, 201) ότι η ονομασία Νέμεσος προήλθε από το «ανάμεσος», υποδηλώνοντας την πόλη την ευρισκόμενη ανάμεσα σε δύο άλλες, το Κούριον και την Αμαθούντα, είναι ενδιαφέρουσα, αλλά γεωγραφικά δεν υπάρχει οικισμός που να μην ευρίσκεται μεταξύ άλλων. Όσο δε για την άποψη ότι η ονομασία προήλθε από τη θεά Νέμεσιν των αρχαίων, αυτή δεν αιτιολογείται ικανοποιητικά. Εξάλλου η ονομασία Νέμεσος απαντάται κατά τα Βυζαντινά Χρόνια και όχι ενωρίτερα. Εδώ προτείνουμε μία άλλη άποψη: ότι η ονομασία Νέμεσος (απ' όπου Λεμεσός) πιθανώς ήταν αρχικά (κατά τους Βυζαντινούς Χρόνους) αγιολογική, προερχόμενη από το όνομα του αγίου Νεμεσίου.
Ο άγιος Νεμέσιος, τοπικός μάλιστα άγιος της Κύπρου, αγνώστου εποχής, ετιμάτο μαζί με τους Ποτάμιον και Δίδυμον. Φαίνεται δε ότι η λατρεία του αγίου Νεμεσίου στην Κύπρο ήταν σημαντική και ευρύτατα διαδεδομένη, εφόσον αυτός είχε περιληφθεί το 1248 στον κατάλογο του παπικού ληγάτου Όδωνος ντε Σιατερώ των (επιλεγμένων) Κυπρίων αγίων που έπρεπε να τιμώνται και από τη Λατινική Εκκλησία. Άγιος Νεμέσιος ήταν, λοιπόν, η ονομασία του αρχικού μικρού οικισμού των Βυζαντινών Χρόνων, απ' όπου αργότερα απλώς Νεμέσιος και τελικά Νεμεσός - Λεμεσός.