Η Επισκοπή Σόλων, σύμφωνα με τον βίο του Αγίου Αυξιβίου, ιδρύθηκε το έτος 57, όταν, μετά τον μαρτυρικό θάνατο του Αποστόλου Βαρνάβα, ο Μάρκος, καταδιωκόμενος από τους Εβραίους της Σαλαμίνας έφθασε στον Λιμνίτη που ήταν το επίνειο των Σόλων, για να εγκαταλείψει την Κύπρο. Ο Μάρκος συνάντησε στον Λιμνίτη τον Αυξίβιο που μόλις είχε φθάσει από την Ρώμη και βλέποντας την θερμή πίστη του Αυξίβιου τον βάπτισε και αφού τον χειροτόνησε επίσκοπο τον έστειλε να διδάξει τον Χριστιανισμό στους Σόλους, που ήταν σημαντική πόλη, κέντρο των μεταλλευτικών επιχειρήσεων στην Κύπρο.