Gaziantep Kalesi'nin yapılışına dair halk arasında yaygın olarak anlatılan efsaneye göre kaleyi zengin bir kadın yaptırıyormuş. Bir gün sokağa çıkmış ve yolda kalabalık insan topluluğunun bir cenaze götürüşüne rastlamış. Yanındaki uşağına dönerek “Bu nedir?” diye sormuş. Uşak ise “Efendim insanlar bir gün gelir ölürler, ölülerini de böyle tabut içinde taşıyarak mezarlığa götürür ve toprağa gömerler. Gördüğünüz tabutun içinde dün bizim gibi canlı olan bir insan cesedi var.” der. Bunun üzerine zengin kadın uşağıyla beraber geri döner ve kaleyi yapan ustaları yanına çağırarak; “Bırakın kale yarım kalsın, ben ölümü hiç düşünmezdim.” der.

Gaziantep Kalesi'nin tarihi eski çağlara kadar uzanıp gitmektedir ancak bu halk arasında anlatılan bu efsanede kesin bir tarih yoktur.