Σύμφωνα με την παράδοση το χωριό Χολέτρια έχει ζωή 500 περίπου χρόνων. Ο πρώτος χώρος ίδρυσης των Χολετριών στα πολύ παλιά χρόνια ήταν η τοποθεσία Αγία Ειρήνη, που βρίσκεται πολύ κοντά στο σημερινό χωριό. Στην τοποθεσία αυτή σώζονται μέχρι σήμερα ένα μισοχαλασμένο εκκλησάκι, τα χαλάσματα κάποιων σπιτιών και ένας ελιόμυλος.

Ο κύριος λόγος εγκατάλειψης της τοποθεσίας Αγία Ειρήνη είναι το ότι βρισκόταν σε ύψωμα απέναντι από την θάλασσα και ήταν μεγάλο μειονέκτημα για την εποχή εκείνη. Οι Σαρακηνοί και άλλοι επιδρομείς εντόπιζαν εύκολα το χωριό και προσαράζοντας στις ακτές έκαναν επιθέσεις και λεηλασίες.

Οι κάτοικοι τότε αναγκάστηκαν για μεγαλύτερη ασφάλεια, να μετοικήσουν σε άλλο σημείο, που σήμερα ονομάζεται «παλιό χωριό», μέσα στην κοιλάδα του Ξηρού, προφυλαγμένοι από τα γύρω βουνά, με άφθονο νερό και γόνιμο έδαφος.

Το χωριό, όπως κτίστηκε στους πρόποδες των δύο βουνών και στις όχθες του ποταμού Ξερού, έμοιαζε με μια μεγάλη χολέτρα λόγω της σχισμής και της μορφής του εδάφους. Από αυτή την ιδιομορφία του χώρου πιστεύεται ότι πήρε και η κοινότητα το όνομα της.

Οι πρώτοι κάτοικοι του χωριού ήταν όλοι κτηνοτρόφοι. Σιγά-σιγά άρχισαν να ασχολούνται και με την γεωργία.

Στις 10 Σεπτεμβρίου 1953 ένας ισχυρός σεισμός συγκλόνισε την επαρχία της Πάφου με αποτέλεσμα αρκετά χωριά να καταστραφούν και τα Χολέτρια να υποστούν σοβαρότατες ζημιές. Παρά τις προσπάθειες των κατοίκων για μετακίνηση του χωριού σε νέα περιοχή η αποικιακή κυβέρνηση δεν έδειξε το ανάλογο ενδιαφέρον. Έγιναν ορισμένες επιδιορθώσεις σε σπίτια που έπαθαν ζημιές και κτίστηκαν μερικές παράγκες στη θέση των σπιτιών που καταστράφηκαν και η ζωή συνεχίστηκε. Αυτό όμως οδήγησε στην σταδιακή εγκατάλειψη της κοινότητας.

Το 1967 ο χειμώνας ήρθε βαρύς. Οι αλλεπάλληλες και δυνατές βροχοπτώσεις προκάλεσαν κατολισθήσεις οι οποίες ήταν μεγάλες και επικίνδυνες για την ζωή των κατοίκων. Ο χειμώνας του 1968-69 ήταν εξίσου βαρύς και η κατάσταση επιδεινώθηκε. Υπήρξαν αρκετές περιπτώσεις που σπίτια έπεσαν εξαιτίας των κατολισθήσεων και η ανάγκη για μετακίνηση του χωριού ήταν πλέον επείγουσα. Οι κάτοικοι του χωριού πίεζαν την τότε κυβέρνηση και όσους μπορούσαν να δώσουν μια λύση στο πρόβλημα που αντιμετώπιζαν. Έφτασαν μέχρι και στον τότε πρόεδρο της Δημοκρατίας τον Αρχιεπίσκοπο Μακάριο ο οποίος έδωσε την υπόσχεση του για την μετακίνηση του χωριού.

Οι εργασίες για την μετοίκιση των Χολετριών άρχισαν στις 10 Μαρτίου του 1971. Σταμάτησαν όμως τον θλιβερό Ιούλιο του 1974 για να αρχίζουν και πάλι στις 19 Αυγούστου του 1974. Οι εργασίες συνεχίστηκαν εντατικά και στις 11 Ιανουαρίου 1975 η πρώτη οικογένεια εγκαταστάθηκε στο νέο χωριό για να ακολουθήσουν και άλλες. Στις 17 Ιουλίου 1975 το νέο χωριό ηλεκτροδοτήθηκε και μέχρι τέλος του ιδίου χρόνου όλες οι οικογένειες μετοίκησαν στο νέο χωριό.

Το χωριό βρίσκεται 22 χιλιόμετρα ανατολικά της Πάφου και είναι κτισμένο σε μέσο υψόμετρο 150 μέτρων, δέχεται μια μέση ετήσια βροχόπτωση γύρω στα 480 χιλιοστόμετρα και στην περιοχή του καλλιεργούνται αμπέλια οινοποιήσιμων ποικιλιών, σιτηρά, ελιές, χαρουπιές και εσπεριδοειδή. Η Χολέτρια συνδέεται οδικώς στα δυτικά με τα χωριά Νατά και Αναρίτα και από εκεί με την Πάφο και στα Νότια με την Νικόκλεια και Τίμη και στα βόρεια με τα χωριά Σταυροκόννου και Κελοκέδαρα.

Η κοινότητα στην διάρκεια της μακράς ιστορίας της γνώρισε αρκετές πληθυσμιακές ανακατατάξεις. Οι κάτοικοι της το 1881 ήταν 103 που αυξήθηκαν στους 149 το 1901, στους 235 το 1921, στους 313 το 1946 και στους 356 το 1960. Στη συνέχεια το χωριό, όπως και όλα τα χωριά της περιοχής θα κτυπηθεί από την αστυφιλία με αποτέλεσμα οι κάτοικοι του να μειωθούν στους 226 το 1976 και στους 257 το 1982. Στην απογραφή του 2001 οι κάτοικοι του χωριού αριθμούσαν τους 241.

Η Χολέτρια σε όλες τις εποχές του χρόνου έχει να προσφέρει στον επισκέπτη μοναδικές φυσικές ομορφιές. Την άνοιξη όλη η περιοχή του χωριού είναι γεμάτη με άγρια λουλούδια, το καλοκαίρι το κατακίτρινο τοπίο από τα θερισμένα χωράφια δίδει μια άλλη παράξενη ομορφιά, το φθινόπωρο με το δροσερό αεράκι χαρίζει μια νότα γαλήνης και ηρεμίας ενώ τον χειμώνα αντικρίζεις το Τροόδος με τα χιόνια του στις κορυφές του και την ομίχλη που επικρατεί εκεί δίδει μια άλλη γεύση του πανέμορφου κυπριακού τοπίου.