La història de Paüls encara està per fer. Els orígens d'aquest poble són incerts. Els filòlegs Montoliu i Alcover Moll afirmen que el topònim prové de la paraula llatina paludes (estanys, llacunes), per la qual cosa, seria possible afirmar un origen anterior a la conquesta àrab. Emili Morera esmenta una troballa de monedes visigòtiques, així doncs, es podria atribuir a aquest període la fundació del poble. Per tant, podria ser que el poble existís ans del "repoblament" català. 

Els documents conservats sobre Paüls i el seu castell són nombrosos, tant a l'Arxiu Municipal de Tortosa com a l'Arxiu de la Corona d'Aragó. Malauradament, no hem pogut consultar-los directament i ens hem limitat a buidar les fitxes que hi fan referència a ambdós arxius. D'altra banda, manca documentació sobre l'església i la parròquia, fins al punt que, la carpeta corresponent de l'Arxiu diocesà és buida. Tan sols, podem referir-nos a la petita monografia sobre la parròquia escrita per mossèn Antoni Bordàs.

Enric Bayerri afirma que poc després de la conquesta catalana de Tortosa, l'any 1148, el comte Ramon Berenguer IV donà el lloc de Paüls al cavaller Roger Despuig, però no mostra la font d'on va treure aquesta informació, amb la qual cosa sembla dubtosa. La primera notícia documental data del 26 de juliol del 1168, quan el rei Alfons I, el senescal Guillem Ramon de Montcada, Ramon de Montcada i Pere de Subirats estengueren una carta de donació del castell de Paüls (Peduls), els seus termes i pertinences, a favor de Guerau de Riu, Pere de Santmartí i Ramon de Queralt, per tal que poblessin el lloc segons els furs de Saragossa. Pere de Subirats retenia una parellada de terra i la tercera part dels drets del castell.

El 1205, Pere el Catòlic traspassà la senyoria que hi tenia a Drogo de Verdeyo, excepte la fidelitat a la seva persona i els drets reconeguts a Tortosa en la carta de poblament. El 1211, Drogo, també rebé del bisbe de Tortosa, el terç dels delmes del terme de Paüls.  A partir del 1228,  la senyoria sobre el poble passà a la família Despuig. Joan Despuig, al 1293, va atorgar una carta de poblament als propis veïns del poble, a raó dels conflictes sorgits per les terres, les cases, etc.  Els Despuig van continuar vinculats com a barons, fins al segle XVII.

La documentació corresponent a les darreries del segle XIII i al segle XIV és particularment abundant, atès que s'hi produeixen constants conflictes de competències i de jurisdiccions, entre el senyor de Paüls i la ciutat de Tortosa. El 1290, el senyor de Paüls impedeix als paers i al veguer de Tortosa la persecució d'uns lladres que havien entrat al terme. Davant les protestes, sembla ser que el senyor de Paüls lliurà els lladres, però s'interposà un plet sobre el terme i la jurisdicció acabà sent resolta, per una sentència de Jaume II el 1303. El 1305 es divideix el bosc de Paüls en tres parts per a Tortosa i una per a Paüls. A l'agost del 1321, la ciutat de Tortosa protestarà al senyor de Paüls sobre uns homes presos. Al mes següent, els paers demanen comparèixer davant el rei perquè Bernat Despuig, senyor de Paüls, els acusa d'haver obert un procés contra Domingo Piquer, que havia desflorat a dues noies de Paüls forçant les seves cases. El 1338 hi ha una altra disputa entre Tortosa i Paüls sobre jurisdicció i el 1366 s'aconseguí la delimitació dels termes amb Alfara de Carles.  El 1367 Tortosa fa obres d'ampliació de la muralla i exigeix l'ajut dels pobles del seu territori, cosa que motivarà una sentència arbitral sobre la participació dels homes de Paüls. El 1372, una altra sentència arbitral delimità el terme de Tortosa amb Paüls i d'altres pobles.  El 1383, Pere el Cerimoniós vengué el domini directe i altres drets de Carles i de Paüls a un mercader de Saragossa, Joan Sancho, per 12.100 sous. Els fogatges més antics es registren, des del 1380, entre 33 i 34 focs. El 1718 tenia 227 habitants i el 1830, 497. 

El 1834, durant la primera guerra carlina, un escamot de 300 carlins es féu fort al castell, que fou conquerit pel coronel liberal Santa Cruz. Probablement, en aquest moment fou destruïda la major part de l'edifici. El 1836, el poble fou saquejat i incendiat pels liberals, consegüentment,  es van perdre els arxius.

Després d'aquest episodi, la població seguí un ritme ascendent fins al tombant de segle, quan assolí els 1241 habitants arribant a funcionar catorze almàsseres, un molí de farina i una fàbrica de maons.

Des del 1920,  el poble visquè un greu declivi econòmic i demogràfic. A la darrera guerra civil, el poble quedà a la línia de front durant la batalla de l'Ebre,  foren cremats els altars de l'església parroquial, que encara era la del castell.

L'origen de la parròquia de Paüls s'ha de remuntar a la conquesta, si bé no en tenim documentació directa. Tanmateix, l'11 de setembre de 1321 se'n segregà la parròquia de Xerta, a instància de Bernat Despuig, senyor del castell de Paüls.  L'església està dedicada a la Nativitat de la Verge; és d'estil gòtic, el qual es pot apreciar en la porta adovellada i en les finestres de mig punt, que encara resten en peu.  Aquesta es troba adherida al castell de Paüls (Peduls). Les restes del castell estan força malmeses, ja que, solament es conserva part de la muralla perimetral i un edifici ( l'església de Santa Maria). Respecte a la situació del castell es molt estratègica, gràcies a que domina àmpliament el poble i el terme, a més a més, es troba prop de l'estretament de la Vall de l'Ebre, de manera que, els era més fàcil poder controlar el comerç fluvial.