L’attuale chiesa parrocchiale dedicata a San Vincenzo Martire (patrono di Orroli) e Sant’Anastasia conserva in buona parte i caratteri architettonici gotico-aragonesi del Cinquecento (per la precisione 1582 come da iscrizione sul capitello destro dell’arcone gotico) anche se realizzata su preesistenti strutture cultuali databili al XII secolo.
Sempre del Cinquecento è l’imponente torre campanaria a canna quadrata, realizzata in porfido rosso e dotata di monofore a sesto acuto ornate da archetti pensili. La facciata, che si configura con terminale piano su cui poggia un’interrotta teoria di merli lanceolati, è tipizzata dal bel portale impreziosito da fregi di gusto moresco.
Anticamente, nel sagrato della chiesa c’era un cimitero ed un ossario.
La chiesa ospita al suo interno una bellissima esposizione di paramenti sacri.
Il santo, patrono del paese, viene festeggiato il 22 gennaio; già dal secolo scorso le celebrazioni in onore del santo erano soltanto religiose: la festa era preceduta dalla novena, veniva celebrata la messa da più sacerdoti, la processione si teneva la sera del 21 gennaio e no veniva nominato nessun obriere ma veniva offerto un piccolo rinfresco da parte del sacerdote.