La collina posillipiana sin da epoca antica, era la sede preferita dai poeti, il luogo di riposo degli stranieri, ed era soprattutto la tappa terminale dei fedeli che scendevano il monte in un succedersi continuo di pellegrinaggi, culminanti sempre e quasi nella fondazione di cappelle votive e di tempietti.

Il tempio dedicato a S. Strato deve la nascita ad uno dei tanti pellegrinaggi. Sorse, infatti, come modestissima cappella sui resti di un antico tempio romano e ne furono fondatori tre greci convertiti, i quali raccolsero il denaro necessario esibendosi come giullari in un piccolo casotto che aveva la propria sede al "Largo del Castello". Il tempietto, la cui origine risale al 1266, occupava un'area oscillante tra i venti ed i venticinque metri quadrati, e rimase nelle condizioni estetiche primitive fino al 1572, anno in cui venne ampliato ed affrescato per volere di don Giovanni Leonardo Basso, abate di S. Giovanni Maggiore, che lo destinò a "grancia", ovvero dipendenza, della propria parrocchia la quale estendeva la giurisdizione ecclesiastica fino a quel ciglio della collina da cui questa precipita sulla spiaggia di Trentaremi.

Nel 1597 la Chiesa, che aveva ormai perduta la vecchia impronta, venne eretta Parrocchia dal Cardinale Alfonso Gesualdo e dedicata a S. Maria delle Grazie in S. Strato, conservando però l'altare dell'antica cappella fino al 1728 allorché un altro altare più spazioso fu costruito. Su di esso fu collocato un quadro raffigurante il martire con la Madonna delle Grazie e San Francesco di Paola. Un altro simulacro del santo è collocato su di un altare laterale della navata centrale. E' una scultura in legno, opera di Giacomo Colombo discepolo del Solimena del VII secolo.

Nel corso dei secoli successivi, la Chiesa ha mantenuto intatte le linee architettoniche, ma ha subito danni alla struttura in seguito al terremoto del 1930 e 1980. Quest'ultimo ha causato la chiusura al culto della stessa, sino al dicembre 1982, data in cui fu riaperta solennemente ai fedeli dopo il restauro.