Secondo la leggenda, gli apostoli Pietro e Paolo, nei primi anni della loro predicazione, passarono per la città di Plestia chiedendo rifugio in una notte fredda e piovosa. Nessuno offrì loro aiuto, tranne una giovane donna sola, dalla quale i due apostoli, per rispetto, accettarono soltanto del pane, rifiutando l’alloggio.
Si incamminarono allora verso il monte Trella, lungo la via della Spina, che collegava Plestia alla Valle Umbra. Quando furono ormai lontani, l’ira di Dio si abbatté sulla città: un tremendo terremoto e un violento acquazzone provocarono la distruzione e l’allagamento dell’abitato, causando la morte di tutti gli abitanti.
La mattina seguente gli apostoli, affacciandosi dal monte, videro che al posto della città si estendeva un grande lago. Ridiscesero quindi a valle per predicare il castigo divino ai pochi superstiti, tra i quali ritrovarono la giovane donna. Sulle rovine di Plestia venne poi costruita una chiesa cristiana.

La Basilica si trova nel luogo dove sorgeva l’antica città umbra di Plestia, scomparsa nel X secolo. L’edificio fu costruito sulla cripta paleocristiana e sui resti di un tempio romano, da cui provengono molti dei materiali da costruzione reimpiegati.
La sua struttura è semplice, a pianta rettangolare, scandita da un ordine di colonne. Non presenta particolari elementi decorativi, ma conserva grande valore storico e simbolico. All’esterno sono visibili i resti di un elegante porticato, testimonianza della rilevanza del sito in epoca medievale.

Dal punto di vista civile, il corpo della basilica appartiene al seminario di Nocera Umbra e ricade nel territorio comunale di Serravalle di Chienti, mentre il sagrato, con la colonna d’angolo del portico, si trova nel comune di Foligno. La sua collocazione unica la pone esattamente al crocevia delle diocesi di Camerino, Nocera Umbra e Foligno. La gestione è affidata all’arcidiocesi di Camerino, mentre la parrocchia di Colfiorito (diocesi di Foligno) mantiene un diritto d’uso su parte dell’edificio.
Fino al 1984, l’intera chiesa faceva parte della diocesi di Nocera Umbra. Con la riforma delle circoscrizioni ecclesiastiche, i territori in provincia di Macerata sono passati alla giurisdizione di Camerino. La colonna del porticato, tuttora in territorio folignate, è simbolo del diritto d’uso mantenuto dalla diocesi di Foligno, ribadito anche negli anni Trenta con una solenne celebrazione presieduta dal vescovo Stefano Corbini.
Le fonti storiche ricordano che la diocesi di Plestia ebbe vita fino al 1006, quando venne suddivisa tra Foligno e Nocera. La chiesa fu poi attribuita a Foligno nel 1138, ma già nel 1200 risultava ceduta a Nocera Umbra.

L’area conserva importantissime testimonianze archeologiche, a circa 300 metri dalla basilica, lungo la via di Val Vaccagna, si trova un santuario dedicato a Cupra, antica dea madre umbra venerata come protettrice dei Plestini. Il tempio, attivo dal VI secolo a.C., fu identificato grazie al ritrovamento di quattro lamine bronzee del IV secolo a.C., scoperte nel 1962. Inoltre, scavi condotti nella cripta della chiesa hanno portato alla luce resti di un villaggio dell’età del Ferro, databile all’VIII secolo a.C.