Una leggenda, riferita dal Fazello, ha come protagonista un coraggioso cavaliere normanno. Nell'anno 1071, durante l'assedio della città da parte dei normanni, gli Arabi, che tenevano saldamente in mano la città, si sentivano tanto sicuri da beffeggiare, dall'alto delle mura, le truppe capitanate da Ruggero e da Roberto il Guiscardo, e tenevano addirittura aperte le porte urbane.
"Mentre si combatteva, un cavaliere normanno (...) fece un atto veramente memorabile, e fu che vedendo la porta della città aperta, per vituperio dei nostri, volle con disprezzo ricompensare l'altro e, spronato il cavallo, entrò con grande impeto nella città, ed uccise uno con la lancia che era a guardia della porta; e (...) passò per mezzo dei nemici, e cavalcando per vie incognite a lui, che non vi era mai stato, arrivò finalmente all'altra porta ed uscì fuori, e ritornò salvo nel campo al suo capitano". Secondo il Padre Amato la porta dalla quale uscì il valoroso cavaliere era quella di Sant'Agata.
Verosimilmente la porta ha preso il nome di Sant'Agata per la vicinanza dell'omonima chiesa che sorge lungo la via del Vespro. In quel luogo, secondo la tradizione, la martire cristiana, nell'uscire dalla città nell'anno 253, per recarsi a Catania dove avrebbe subito il martirio, si sarebbe fermata per allacciarsi un calzare, lasciando l'impronta del piede su di un sasso. E qui fu innalzata una chiesa detta per questo "Sant'Agata de petra" o "Sant'Agata la pedata", chiesa certamente molto antica, tanto da non esserci notizie della sua fondazione.
Si può supporre che tale nome sia stato dato alla porta tra il 1071 (data della cessazione del dominio arabo) e il 1178, cosa che indurrebbe a pensare che la porta sia stata aperta nel primo periodo della dominazione normanna. La porta comunque risulta già citata in alcuni atti di vendita del 1275. Da porta Sant'Agata il 31 marzo 1282 uscì il popolo palermitano per andare a festeggiare i Vespri, e dalla stessa porta rientrò la moltitudine agitata, insorta contro gli Angioini con quella sommossa conosciuta col nome di Vespri Siciliani.
L'architettura della porta è molto antica, anche se non è facile affermare che essa sia quella originaria del periodo normanno. Il Di Giovanni, nella topografia di
Palermo, precisa però a tal proposito che da nessun documento risulta che sia stata rifatta. È quindi essa una delle più antiche testimonianze della cinta muraria medioevale, che si conserva in discrete condizioni. Poche tracce restano dell'affresco raffigurante la Madonna del Carmine, dipinto nella volta, e delle figure di angeli che si trovavano nelle lunette.
La porta è composta da pietre ad intaglio con due archi, uno più sporgente che termina a punta, l'altro più dentro al vano della porta che è tondeggiante. Si nota l'influenza della fiorita cultura araba e bizantina, nella ricercata eleganza degli archi, nel taglio della pietra, nell'effetto chiaroscurale dosato, dovuto alle sporgenze di alcune strutture rispetto ad altre più incassate, e infine negli affreschi che, contrastando col colore della pietra tufacea, assumevano toni molto raffinati.
