Ο Όσιος Θεοσέβιος γεννήθηκε στο μικρό χωριό Μελάνδρα, 12 χιλιόμετρα Νοτιοανατολικά της αρχαίας Αρσινόης, της σημερινής Πόλης της Χρυσοχούς της επαρχίας Πάφου, από γονείς ευσεβείς και εύπορους, τον Μιχαήλ και την Άννα. Είχε δε αδελφό τον όσιο Αρκάδιο τον μετέπειτα επίσκοπο Αρσινόης. Η ακριβής χρονολογία της γέννησής του µας είναι άγνωστη. Θα πρέπει όμως να τοποθετείται στα τέλη του 4ου µ.Χ. αιώνα, αν δεχτούμε, σύμφωνα µε τους επισκοπικούς καταλόγους της περιοχής, ότι ο αδελφός του Αρκάδιος ήταν επίσκοπος της Αρσινόης στις αρχές του 5ου αιώνα μ.Χ.

Αν και ο αδελφός του πήγε στην Κωνσταντινούπολη για να σπουδάσει, αυτός έμεινε κοντά στους γονείς του και έγινε βοσκός. Ποιμαίνοντας τα πρόβατά του, είχε την ευκαιρία να επιδίδεται στην προσευχή, τη μελέτη του λόγου του Θεού και άλλες αρετές. Με πρόφαση τη βοσκή των προβάτων προχωρούσε στο βουνό σε µια απόσταση 3 χιλιομέτρων από το χωριό του και σε τόπο ήσυχο και απόμερο προσευχόταν απερίσπαστα. Εντόπισε μάλιστα στην περιοχή και κάποιο σπήλαιο στο οποίο πολύ συχνά εισερχόταν και µε νηστείες και γονυκλισίες προσευχόταν στο Θεό.

Ο Όσιος Θεοσέβιος έτρωγε ελάχιστα, µόνο για να ζει. Τις µέρες της νηστείας μοίραζε όλη την τροφή που έπαιρνε μαζί του, που ήταν συνήθως µόνο ψωμί, σ' όσους έβρισκε μπροστά του και είχαν ανάγκη. Κι αν δεν έβρισκε κανένα τέτοιο άνθρωπο μπροστά του, έδινε το ψωμί του στα πουλιά, για να μην αθετεί την εντολή της νηστείας.

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

Κάποια µέρα, διαισθανόμενος το τέλος του, ίσως αυτό να του μηνύθηκε κατά κάποιο τρόπο από το Θεό, ο Θεοσέβιος κάλεσε τη γυναίκα του και µε τρόπο παραβολικό της είπε ότι φεύγει πιο μακριά για βόσκηση των προβάτων κι εκεί θα μείνει για αρκετό χρόνο. Την προέτρεψε να συνεχίσει την προσπάθεια της τελείωσης µε υπομονή και σωφροσύνη παραμένουσα είτε στο σπίτι τους στη Μελάνδρα είτε μεταβαίνουσα στη Φιλούσα, κοντά στους γονείς της. Κι αφού αντάλλαξαν σκέψεις για την αιώνια ζωή αναχώρησε στο τόπο της προσευχής. Άφησε το κοπάδι να βόσκει κι αυτός προχώρησε στο σπήλαιο, προσευχήθηκε µε θέρμη και εκεί ήρεμα παρέδωσε το πνεύμα στο Θεό. Ήταν 12 Οκτωβρίου.

Ο σκύλος του Αγίου, που βρισκόταν στο στόμιο του σπηλαίου σα να εκτελούσε χρέη θυρωρού, μάζεψε την επόμενη µέρα το κοπάδι και το οδήγησε στη Μελάνδρα. Οι γονείς και η σύζυγος του Αγίου βλέποντας το κοπάδι χωρίς τον ίδιο, ανησύχησαν. Τον αναζήτησαν στη Φιλούσα κι όταν δεν τον βρήκαν, καθοδηγούμενοι από το σκύλο του, έφτασαν μετά τρεις µέρες στο σπήλαιο. Εκεί βρήκαν το λείψανο του Αγίου να ευωδιάζει. Κι επειδή δεν μπόρεσαν να το μετακινήσουν και να το μεταφέρουν στο χωριό για ταφή, κι επειδή είχε ήδη νυχτώσει, έμειναν το βράδυ στο µέρος εκείνο, λογαριάζοντας να επιχειρήσουν τη μεταφορά την εποµένη. Φάνηκε όμως το βράδυ εκείνο ο Άγιος στον πατέρα του και του ζήτησε να τον θάψει εκεί. Πράγματι τον κήδεψαν εκεί όπου και αργότερα κτίστηκε ναός επ' ονόµατί του. Ο ναός του έγινε καταφύγιο πολλών Χριστιανών τόσο από τα γύρω όσο και τα μακρινότερα χωριά. Κατέφευγαν σ' αυτό µε πίστη και θεραπεύονταν από διάφορες ασθένειες κι έπαιρναν κουράγιο και δύναμη για συνέχιση του πνευματικού αγώνα.

Ο Άγιος Νεόφυτος αναφέρει πάµπολλα θαύματα που έγιναν από τον Άγιο Θεοσέβιο µετά το θάνατό του. Κατά τρόπο θαυμαστό υπέδειξε σε μοναχό που ήθελε να κτίσει κελιά κοντά στο ναό του, τον τόπο όπου υπήρχε ασβέστης τον οποίο και βρήκε και χρησιμοποίησε. Προστάτεψε το μικρό περιβόλι του ίδιου μοναχού από τους κόρακες, πάλι µε τρόπο πρωτάκουστο. Άνοιξε οφθαλμούς τυφλών και θεράπευσε κωφούς. Κάποτε, δύο βοσκοί σύλησαν τον Ναό του Αγίου, ωμολόγησαν την αμαρτία τους, επέστρεψαν όσα έκλεψαν και ζήτησαν και πήραν συγχώρεση. Κι άλλα πολλά ενεργεί μέχρι τις µέρες µας ο Άγιος Θεοσέβιος µε τη βοήθεια του Θεού.

Στις µέρες µας επιδεικνύεται ακόμη «το σπήλαιον του Αγίου Θεοσεβίου».

Εν τω άντρω Μελάνδρας ασκησάµενος Όσιε και προς ουρανόν την πορείαν εκείθεν πάτερ ποιησάµενος, τοις τέκνοις σου ηµίν, ως αληθώς εγένου τύπος αρετής και πίστεως, εγκρατεία εκδιδάσκων τας των παθών ορµάς συστέλλειν Θεοσέβιε. Δοξα τω σε στεφανώσαντι Χριστώ, δόξα τω και ηµίν σε φανερώσαντι, δόξα τω αναδείξαντί σε Αρσινόης καύχηµα.