È sorta sui ruderi della chiesa di S. Maria dei Francesi intorno al 1690. Sulla porta laterale della chiesa è presente una lapide risalente al XVIII secolo, in cui si ricorda il culto di S. Cesareo e di S. Aloi, con una sintetica storia dell’edificio.

La sua struttura consta di una unica ampia navata, e perciò molto capiente. Nella facciata principale, rivolta verso la rupe che domina tutto il territorio circostante, sono collocate quattro statue, realizzate recentemente dallo scultore contemporaneo Romolo Rizzuti, collocate in altrettante nicchie, vi sono raffigurati, nell’ordine: S. Francesco di Paola, S. Sebastiano, patrono di Petilia, S. Pietro e S. Paolo. L’abside è una delle attrattive della chiesa: è decorata da un grande mosaico, realizzato nel 1970 da artisti fiorentini, e raffigura Gesù in mezzo ai discepoli.

La chiesa ospitava i culti dell’Annunziata e di S. Leonardo; ora ospita quello di S. Francesco di Paola, che dal 1946 divenne co-protettore di Petilia. Intorno al 1830 e fino al 1860 la chiesa fu retta dai padri "Ritirati", che la fecero assurgere a vero e proprio centro culturale del paese