La chiesa di San Paolo spicca fra gli agrumeti della piana di Milis e colpisce per via della spettacolare facciata, costruita in opera bicroma, cioè alternando filari di pietra calcarea chiara a filari di scuro basalto. Il titolo di "sanctu Paulu de Miili" è documentato nel "Condaghe di Santa Maria di Bonarcado" (XII-XIII secolo). La diversità di materiali (calcari, vulcaniti, basalti e tufo verdognolo) indica la possibilità che alla costruzione della chiesa abbiano operato maestranze diverse. La stessa tecnica edilizia mostra discontinuità, per cui si può ipotizzare che alle prime maestranze, legate al cantiere della cattedrale di Santa Giusta e operanti alla metà del XII secolo, si debbano l'impianto e il telaio strutturale caratterizzato da larghe paraste angolari e dallo zoccolo a scarpa che corre lungo tutto il perimetro. Alle maestranze che operavano in Arborea nel primo quarto del XIII secolo si devono quelle parti in opera bicroma di basalto e calcare dorato messa in opera con regolarità specie nella facciata. La chiesa di San Paolo ha pianta longitudinale di circa 24 m. Il tipo è classificabile come croce "commissa", con abside a S/E. Ai due terzi della lunghezza la navata principale interseca perpendicolarmente un braccio molto più corto della navata, con funzione di transetto. Sul lato N/E al braccio del transetto e lungo la navata principale si innesta un corpo estraneo al perimetro cruciforme. La copertura è a capriate lignee nella navata centrale e a crociera nel transetto e nel vano N/E. La facciata riceve slancio dalle due lesene ai lati del portale che con i pilastri angolari partiscono la facciata in tre specchi conclusi da arcate modanate a tutto sesto. Quella centrale ospita un oculo modanato, quelle laterali rombi gradinati. L'unico portale in facciata è del tipo achitravato con architrave timpanata e lunetta a tutto sesto. Lungo tutto il perimetro della chiesa, compresa l'abside, corre una serie di archetti a tutto sesto modanati di diverse dimensioni, impostati su peducci lavorati, a loro volta liberi o gravanti su lesene o pilastri angolari.