La chiesa sta subito oltre il ponte vecchio, sulla riva est, e quasi tutti le passano davanti. È ciò che resta dell'unico convento dei paolini in Algarve, l'ordine eremitico della Serra de Ossa, fondato qui nel 1606 come prima casa religiosa su quel lato del Gilão. Il convento fu venduto all'asta dopo il 1834; la chiesa rimase. È costruita nello stile spoglio, arquitetura chã, con una pianta a croce latina che quasi nessun'altra chiesa di Tavira ha. Dentro ci sono sette retabli in legno che non furono mai dorati. Nessuna fonte dice perché. È una chiesa in cui bisogna entrare per capirla, e d'estate viene aperta.
Tavira crebbe oltre le sue mura nel Quattrocento e oltre il fiume fino alla zona di Alagoa. Di là non c'erano conventi prima che arrivassero i paolini. L'Ordem dos Eremitas de São Paulo, un ordine eremitico portoghese della Serra de Ossa, costruì qui la sua unica casa in Algarve nel 1606, proprio accanto al ponte. Il fondatore è sulla facciata: sopra il portale dell'atrio è scolpito "DOMUS DEI EST ET PORTA CELI / PAVLVS ERMITARVM AVCTOR ET MAGISTER", casa di Dio e porta del cielo, Paolo autore e maestro degli eremiti. Il sacerdote e storico José António Pinheiro e Rosa lo definì "un luogo tranquillo, circondato da buone case". Vale ancora.
La facciata guarda a sud: un arco a tutto sesto immette in un atrio profondo e, in alto, un frontone semicircolare porta una croce di ferro. Nel secondo quarto del Settecento il piano superiore ricevette tre finestre per far entrare la luce, e sopra quella centrale fu collocata in una nicchia una statua in terracotta di Nossa Senhora da Ajuda. Lei sta quindi fuori, sulla facciata, non dentro l'atrio. La statua sarebbe arrivata da un altro convento; quale, le fonti non lo dicono. Nella volta dell'atrio c'è uno stucco della stessa epoca: Paolo l'Eremita, patrono del convento, con un leone e una palma, i suoi attributi dal deserto.
La chiesa è a navata unica con transetto e un coro rettangolare. Contiene sette retabli in legno intagliato, e nessuno di essi fu dorato e dipinto come si usava nel barocco. Sono in legno nudo. Perché, le fonti non lo dicono. Il più grande e il più riccamente intagliato è il retablo di Nossa Senhora do Carmo, eseguito nel 1730 dall'intagliatore Gaspar Martins. La confraternita carmelitana aveva sede in una cappella qui prima di avere la propria chiesa nel 1747. Parte dei dipinti e delle statue di santi proviene da chiese e conventi soppressi della città. Il pavimento è il cotto rosso del Seicento, attraversato da piastrelle di ceramica spagnole.
Quando gli ordini furono soppressi nel 1834, la chiesa passò alla Confraria de Nossa Senhora da Ajuda, mentre il convento e il suo giardino furono venduti all'asta. Il comune scrive che gli edifici furono poi demoliti. Non è del tutto esatto. L'inventario dello Stato trova un portale barocco che dà sul giardino del convento, il refettorio e la sacrestia addossati al coro, e ali conventuali diventate abitazioni intorno al 1900. Addossata al coro c'è anche una fila di case del Seicento con doppia gronda, forse l'abitazione del sagrestano. Una procedura di vincolo è andata avanti dal 1983 al 2009 ed è decaduta. La chiesa è senza tutela legale e appartiene alla Diocese do Algarve.
Il comune e l'associazione Artgilão aprono la chiesa d'estate insieme alle altre chiese della città; altri orari non sono indicati. Nel 2018 era nei giorni feriali 10.15-12.20 e 14.30-17.45, quindi controllate gli orari dell'anno. Da fuori si vedono sempre l'iscrizione sopra il portale, la nicchia sopra la finestra centrale e lo stucco di san Paolo nella volta dell'atrio. Girate dietro fino al coro e guardate la fila di case con la doppia gronda.
Nel 1606 la riva est era ancora la periferia di Tavira. La città si era da tempo allargata oltre il ponte, ma nessun ordine vi si era stabilito. I paolini presero il posto proprio accanto al ponte, vicino alla città quanto si poteva senza esserci dentro. È ancora così che la chiesa si presenta: in mezzo a un quartiere di abitazioni, a pochi passi dal ponte, eppure fuori dal percorso.
La chiesa sopravvisse al 1834 perché una confraternita la prese. Gli altari sono ancora in legno nudo, e il pavimento del Seicento c'è ancora. La raccolta di dipinti e statue da chiese soppresse ne fa una specie di deposito della Tavira che è scomparsa. Le ali del convento sono abitazioni, il portale del giardino è in piedi, e la fila di case accanto al coro c'è. Tutto questo senza vincolo. È più interessante di quanto sembri, e più fragile.