Nell'angolo orientale della città, dove i due bracci del fossato punico si incontrano, in posizione elevata rispetto al pendio degradante cittadino, con un grande piano antistante libero da costruzioni rivolto verso la città, sorse il castello medievale. Fondato forse solo come recinto fortificato in età normanna (ma non si può escludere che in tal punti vi fosse una fortezza bizantina), venne rinforzato in età sveva, come attestano l'impianto pseudo-trapezoidale ed alcuni elementi stilistici, quali i costoloni di un ambiente della torre circolare, tipici dell'architettura federiciana. Una lettera del 1239 inviata da Lodi da Federico II di Svevia, dove si invita il giustiziere ultra Salsum (al di là sel Salso) a non effettuare alcuna ristrutturazione nei castelli di Trapani, Marsala, Mazara e Sciacca, e ad affidare a cittadini fidelibus nostris la manutenzione degli stessi per impedirne la rovina, dimostra l'esistenza del Castello agli inizi del secolo XIII.

Il piano del castello era una estesa piazza verso cui confluivano due vie che lambivano le mura orientali ed altre tre vie che si inserivano nel tessuto urbano della città medievale, congingendosi con il tessuto antico. Una di queste, a sud-ovest, l'attuale via Punica, collegava il piano con la sede dell'antica cattedrale. Prospiciente quest'ultima via era visibile fino a pochi anni fa, nell'angolo opposto al cantonale dell'abside della chiesa di San Matteo, un'apertura con mostra di bottega quattro-cinquecentesca - oggi nascosta dall'intonaco e forse non ancora manomessa - a dimostrare la vocazione mercantile della zona intorno alla cattedrale. Dal Castello, oggi occupato da costruzioni ottocentesce lungo il fossato punico, era parte integrante l'odierna piazzetta Sant'Oliva. Tale nome deriva dalla tradizionale ubicazione della prigione in cui la santa, venerata anche dagli Arabi, fu rinchiusa prima della sua riduzione in cattività a Tunisi, dove venne martirizzata e sepolta forse nel luogo ove sorge la Grande Moschea (Djamaa ez Zitouma-La moschea dell'ulivo). Ciò confermerebbe la presenza nella zona del castello di una fortezza oggi scomparsa o riorganizzata in età bizantina e/o normanno-sveva.

Tuttavia è bene sottolineare che i dati dello scavo di vico Infermeria, sebbene parziali e limitati alla superficie, hanno evidenziato, in questa zona, in un periodo definito "altomedievale", la presenza di aree industriali all'aperto, cui fece seguito la costruzione di alcuni ambienti utilitaristici relativi ad abitazioni povere, addossate al muro di cinta lungo il fossato, databili a partire dalla seconda metà del secolo XII. Una di esse poteva essere una bottega artigiana che fabbricava lucerne, rimasta in uso almeno fino all'inizio del XIII secolo, quando, forse per ragioni di sicurezza, vengono abbandonate o abbattute le costruzioni addossate al muro cittadino, creando così di fatto quel vuoto intorno alla fortificazione medievale rimasto invariato almeno fino alla metà del XVIII o agli inizi del XIX.

Oggi, il castello medievale lilybetano ospita la casa circondariale di Marsala, dove nel 1979 venne rinchiuso Roberto Vecchioni, accusato di spaccio di sostanze stupefacenti dal giudice istruttore di Marsala; l'accusa si riferiva ad un episodio avvenuto durante una serata alla Festa dell'Unità di Marsala, nel 1977, quando il cantautore avrebbe offerto uno spinello ad un ragazzo quattordicenne; a seguito delle ammissioni del ragazzo, Vecchioni venne arrestato e rilasciato dopo alcuni giorni. Il ragazzo in seguito ritrattò ma il processo proseguì per concludersi con la sua assoluzione; da questa vicenda personale trasse poi l'ispirazione per scrivere le canzoni "Lettera da Marsala" e "Signor giudice".