Según las actas tardías de su martirio, Restituta nació en una ciudad llamada Poniza, aunque los hagiógrafos piensan que en realidad se trata de Tiniza, es decir el poblado antecedente de la actual Túnez, muy cerca de la antigua Cartago, ciudad donde se consumó, según las mismas actas, el martirio.
A diferencia de los mártires de Abitinia, las actas de Restituta son muy poco fiables en cuanto a su historicidad. Luego de las diferentes pruebas y vejaciones a la que la mártir es sometida, es puesta en una barca a la que se le enciende fuego, para que se hunda en el mar; pero en lugar de hundirse, la pequeña nave arriba (milagrosamente) a la isla de Aenaria, la actual Ischia, frente al golfo de Nápoles. Allí un ángel revela a la descubridora de los restos la procedencia y gesta de la mártir, y es enterrada y venerada.
A la vista de los milagros que se producen en su tumba el culto se va extendiendo, y el propio emperador Constantino (por tanto dentro del mismo siglo IV) manda construir en su honor una basílica en Nápoles, a donde finalmente son trasladados gran parte de los restos, y pasa a ser el principal centro de su culto, hasta hoy.
Ciertamente es difícil explicar cómo llega la mártir cartaginesa a no tener culto en Cartago sino en Nápoles. Más lógica que la explicación de las actas es pensar que el culto de la santa llegó a Nápoles después del 450, es decir, cuando la persecución de los vándalos en África llevó muchos vestigios del cristianismo africano hacia Italia, pero puesto que existe la tradición de la basílica constantiniana (que es por fuerza anterior), esto parece imposible. Sin embargo debe tenerse presente que las actas (que son del siglo X o posterior) no mencionan a Nápoles, y que la primer referencia que tenemos a esta ciudad como centro de culto, aunque pretende remitirse hasta Constantino, es mucho más tardía.
Podemos reconstruir hipoténticamente la cuestión del siguiente modo: hubo una mártir en Cartago, quizás a inicios del siglo IV, persecución de Dioclesiano, quizás de la persecución vandálica de mediados del siglo V. Posiblemente por llevar el mismo nombre que la Restituta que formaba parte del más famoso grupo de los mártires de Abitinia, no tenemos vestigios de un culto separado de ella en África. Sobrevenida la persecución vandálica, sea que haya muerto en ella, sea que ya hubiera sido martirizada siglo y medio antes, su culto arriba, de la mano de algunos creyentes, posiblemente poseedores de alguna reliquia, a las cercanías de Nápoles, a la isla mencionada. Una vez allí la fama de santidad y milagros se afianza -incluso hay registros de milagros de la santa en Sicilia en el siglo XIV-, y se escriben las Actas. Nápoles, como urbe más importante de la región reclama ser el centro de culto, y surge entonces la fabulación de la basílica constantiniana, que consolida la importancia de Nápoles para el derecho de esta ciudad a poseer las reliquias.
Ver Acta Sanctorum, mayo IV, pág. 23ss. El artículo de Vito Calise en Santi e beati se inclina por la hipótesis de un traslado en la persecución vandálica, pero considera que es la Restituta del grupo de Abitinia.