Ιερέας και μάντης του ιερού της Αφροδίτης στην Πάφο. Το όνομά του παραδίδεται μόνο από τον Ρωμαίο ιστορικό Τάκιτο*, ο οποίος το αναφέρει στην αφήγησή του για την επίσκεψη στην Κύπρο του μετέπειτα αυτοκράτορα Τίτου*, γιου του αυτοκράτορα Βεσπασιανού.
Σύμφωνα με την αφήγηση του Τάκιτου, ο Τίτος πήγαινε από την Ελλάδα στην Ιουδαία για να συναντήσει τον πατέρα του (69 μ.Χ.) και στο ταξίδι του αυτό πέρασε από την Κύπρο. Με την ευκαιρία αυτή θέλησε να επισκεφθεί τον ναό της Παφίας Αφροδίτης, που ήταν περίφημος και για τους ντόπιους και για τους ξένους. Εκεί, σφάζοντας πολλά ζώα, ζήτησε μαντεία για το ταξίδι του στην Ιουδαία.
Ο Σώστρατος, που ήταν ιεροσκόπος (σπλαχνοσκόπος), αφού μελέτησε τα σπλάχνα των σφαγίων, είπε στον Τίτο ότι ήταν ευνοϊκά και ότι η θεά έδινε τη συγκατάθεσή της στις ενέργειές του. Στη συνέχεια ο Σώστρατος κάλεσε τον Τίτο σε ιδιαίτερη μυστική συνομιλία και του αποκάλυψε το μέλλον, με αποτέλεσμα ο Τίτος να αφήσει την Κύπρο με αναπτερωμένο το ηθικό του.