La Chiesa parrocchiale, dedicata a S. Stefano diacono e martire e a S. Martino vescovo, è situata in Via Costa Vecchia.
L'attuale parrocchia della Costa risulta dall'unione di due antiche chiese presenti a poca distanza l'una dall'altra: S. Martino di Gallisterna e S. Stefano di Paganico.
La prima chiesa, risalente al XII secolo, cessò di esistere nel 1627, quando titoli e arredi sacri vennero trasportati in quella di S. Stefano. Le prime memorie di questo edificio, invece, risalgono al 1419; esso prese il nome da un fondo o luogo denominato Paganico e Paganego, posto nella curia di Gallisterna. L'appellativo di Paganico rimase alla Chiesa sino al sec. XVI quando si iniziò a chiamare della Costa. La Chiesa aveva una navata laterale con diversi altari intitolati, fra gli altri, a S. Antonio Abate (1508) e a S. Maria di Mirolo (1513). La costruzione di questa cappella, dedicata alla Natività di Maria, dimostra l'antichità della devozione mariana in questa zona; sopra l'altare si trovava una Madonna con Bambino che il vescovo di Imola Ercolani, durante la visita del 1574, ordinò di restaurare. Nel XVI sec. è poi ricordato l'altare del Corpo di Cristo (con quadro raffigurante la Resurrezione di Nostro Signore), mentre nel 1657 ve ne sono tre nuovi: di S. Martino (dopo la distruzione della omonima chiesa), della SS Annunziata e del Rosario. L'altare maggiore era posto sotto una volta dipinta, ma tutta la Chiesa era affrescata. Il battistero, costruito nel 1583 e distrutto nel 1599, fu riedificato nel 1627. La Chiesa attuale, con facciata a ovest, venne ricostruita a volta nel 1690, ampliata di coro e presbiterio, e dipinta da Paolo Costa nel 1906 a cura dell'allora arciprete mons. Bagnara; misura m. 23 X 6,80 e presenta cinque altari. Il primo a destra, dedicato a S. Filippo Neri nel 1865, presenta un quadro di scuola bolognese, mentre il secondo è dedicato alla Beata Vergine del Rosario: in questa cappella, dal 1857 è venerata una statua raffigurante la Madonna del Rosario dello scultore faentino Domenico Utili, statua che andò a sostituire una immagine precedente formata da uno scheletro di legno imbottito di stoffa, con testa, mani e piedi, sia della Vergine che del Bambino, in stucco. L'altare della B. Vergine è poi corredato da numerosi quadretti ex-voto. L'altare maggiore, di scogliola, ha le mensole e il tabernacolo provenienti dalla soppressa Chiesa di S. Giuliano a Imola. Il quadro sovrastante raffigura Il Martirio di S. Stefano, opera pregevole di scuola bolognese. Il quarto altare è dedicato a S. Martino, compatrono della Chiesa, e ai Ss. Antonio Abate e Antonio da Padova, mentre il quinto è dedicato alla Natività della Vergine e presenta un quadro con cornice dorata. L'organo è di Abele Marenzi. La Chiesa della Costa dipese fino al 29 luglio 1791 dalla Pieve di Montemauro, per poi essere aggregata al vicariato di Valsenio, e diventare infine sede di vicariato nel 1792. Nel 1880 mons. Bagnara finanziò la costruzione della Torre campanaria, ultimata tre anni dopo, sulla quale furono poste quattro campane del bolognese Brighenti. La Chiesa, seriamente danneggiata durante la II guerra mondiale, venne restaurata nel dopoguerra.