La storia di Semelia risale a tanto tempo fa, quando i Romani decisero di insediarsi in un territorio vicino alla laguna, costruendo le loro ricche e sontuose ville e decorandole con eleganti capitelli ed elaborati mosaici.

Ancor oggi è possibile osservare resti di costruzioni romane un po' dappertutto, che dimostrano l'esistenza di un'antica Semelia.

Recenti ricerche archeologiche, che hanno rilevato la presenza di materiali epigrafici e di ornato architettonico, confermano l'esistenza di una zona abitata risalente a quell'epoca.

Le favorevoli condizioni climatiche, la vicinanza con il mare, la ricchezza delle acque dei fiumi e la possibilità di sfruttare le risorse della pianura rappresentarono per gli antichi abitanti del piccolo centro motivi validi per decidere di edificare le proprie case in quest'area.

Non si può escludere che anche durante la dominazione bizantina la zona fosse abitata e che proprio in questo periodo sia iniziato il culto rivolto a Santa Caterina di Alessandria, giovane donna colta e amante della filosofia, che ai tempi delle persecuzioni contro i cristiani, fu condannata a morte per la sua fede.

L'attuale chiesa, che forse sorge non solo sulle ville romane ma anche su una preesistente chiesetta bizantina, risale al medioevo, quando i monaci di San Vittore di Marsiglia vennero nel Campidano, invitati dal Giudice di Cagliari, per risollevare le condizioni spirituali, economiche e sociali della Sardegna dopo le invasioni dei Mori.

A Semelia essi misero insieme, grazie alle donazioni dei Giudici e delle famiglie possidenti del tempo, una grande proprietà, i cui confini arrivavano sino all'attuale zona della Marina di Cagliari.

Si ritiene che la chiesetta fosse stata edificata subito dopo l'anno Mille poiché in una bolla del 1289 del Papa Nicolò IV viene confermato il "Privilegium Plumbea Bulla Munitum" concesso il 4 aprile 1095 dall'allora Papa Urbano II alla "ecclesiam Sancte Kateline in Semelia".

I Vittorini di Semelia, ma anche quelli di tutte le zone della Sardegna, in questo periodo, portarono un grande rinnovamento sia da un punto di vista culturale che economico. Avviarono un'intensa attività architettonica restaurando i vecchi edifici e ampliandoli; introdussero nuovi metodi di coltivazione, bonificando ed irrigando i terreni e lavorandoli con ottimi risultati; si dedicarono alla pesca che, data la ricchezza della vicina laguna, doveva rappresentare un lavoro abbastanza fiorente; si occuparono di allevamento, di produzione del sale e non disdegnarono le attività commerciali ed i traffici che costituirono per la comunità religiosa una fonte di reddito non indifferente.

La ricchezza e la laboriosità di questi monaci non potevano che infastidire i Pisani che, per conquistare il controllo sulle saline, dettero battaglia ai Vittorini, specialmente a quelli del Priorato di San Saturno di Cagliari, togliendo loro il monopolio del sale. Iniziò pertanto un periodo di decadenza che i dominatori Aragonesi resero ancora più pesante, tanto che dopo la metà del XIV secolo i Vittorini non avevano più le loro proprietà. Così Semelia passò alla Mensa Arcivescovile di Cagliari, mentre la chiesetta continuava ad essere officiata in alcune occasioni importanti, ma non più dai Monaci Vittorini .

Il piccolo centro andava sempre più spopolandosi come si deduce da una Bolla di Clemente VII del 12 aprile del 1524 in cui si affianca il nome di Santa Caterina di Semelia al nome di San Sebastiano della Villa del Mas. Si suppone, pertanto, che la popolazione si fosse spostata verso l'entroterra e fosse andata via via concentrandosi nel territorio di Elmas.

Nel XVII secolo c'era solo un eremitano che custodiva e curava la chiesa e che si occupava di tutto ciò che poteva essere utile per mantenere il culto. In un'acquasantiera, ancora presente nella chiesa, si può leggere sul bordo circolare di marmo bianco la scritta "Jaume Roca Ermita de S. Catalina".