La struttura catacombale, formatasi probabilmente sulla sede di una preesistente necropoli greco-romana, andò comunque sviluppandosi nell'allora disabitato vallone della Sanità (attuale Rione Sanità) dove, secondo la tradizione, aveva trovato sepoltura san Gaudioso, un vescovo dell'Africa settentrionale naufragato a Napoli e qui vissuto fino alla morte dopo avervi fondato un monastero ed essersi guadagnato fama di santità. La sua tumulazione avvenne fra il 451 e il 453 e il luogo, benché custodisse anche la tomba di un altro vescovo, san Nostriano, divenne oggetto di venerazione nei suoi confronti e noto da allora con il suo nome.

L'accesso alle catacombe si trova nella cripta, o succorpo, sotto il presbiterio rialzato della chiesa intitolata alla Madonna della Sanità, rappresentata in un affresco staccatosi forse da una parete dell'antica chiesa in seguito ad una frana di fango. La Madonna della Sanità (V-VI secolo), probabilmente la più antica raffigurazione mariana di Napoli, è oggi conservata nella prima cappella laterale destra della basilica. Molti abitanti del quartiere credono tuttavia che la chiesa sia intitolata a san Vincenzo Ferreri per via della devozione popolare verso questo santo domenicano e per la bellissima statua lignea che lo rappresenta, posta alla sinistra dell'altare.

Oggi resta solo una piccola porzione di quelle che furono le catacombe originarie.