Auxibio nació en Roma, en el seno de una familia pagana. Su padre deseaba que contrajera matrimonio de acuerdo a la costumbre romana, para asegurar una posición política, pero él estaba más cerca de hacerse cristiano que de pensar en casarse, así que prefirió apartarse del seno familiar.
Fue así como Auxibio llega a Chipre y se encuentra con San Marcos, su tío, de quien sabía había dejado todo para seguir las enseñanzas de un tal Jesús de Nazaret. Eran los tiempos posteriores al martirio de San Bernabé, acontecido en la isla en la década del sesenta. Bernabé, judío levita nacido en Chipre y pariente de Marcos, fue uno de los doce apóstoles de Cristo y el primero en evangelizar la isla. Fue Bernabé quien ganó a Mateo para la causa de Jesucristo.
San Marcos contribuyó enormemente a que Auxibio conozca la fe en Jesucristo y cuando lo vio comprometido realmente le concedió el bautismo. Luego lo instruiría en la tarea de anunciar el Evangelio. Una vez que Auxibio estuvo listo, Marcos lo envió a predicar a la ciudad de Solos, al norte de Chipre. En ese lugar empezó a proclamar el Evangelio, pero con excesiva discreción. Aun así, su vida ejemplar produjo conversiones, entre ellas la de un sacerdote pagano, adorador de Júpiter.
