Battal Gazi ile ilgili menkıbeler, henüz yaşadığı sırada halk arasında yayılmaya başlamıştır. Daha sonra bilinmeyen bir yazar bunları toplamış, Haçlı Seferleri sırasında oluşan başka menkıbelerin de katılmasıyla ``Zatü`l-Himme`` (ve ya ``Zü`l-Himme``) adıyla anılan bir Arap halk öyküsü oluşmuştur. Bu kitapta Battal Gazi ancak ikinci bölümde ortaya çıkar. Birinci bölümde ise onunla ilgili menkıbeler Başkomutan Mesleme bin Abdülmelik`in arkadaşı Sahsah`ın başından geçmiş gibi anlatılır. Ayrıca Hristiyanlarla Müslümanlar arasındaki savaşları konu edinen Bizans halk öyküsü ``Digenis Akritasın da ``Battalname`` ve ``Zatü`l-Himme`` ile benzer yönleri vardır.
Türkçe Battalname`nin 11. yüzyıl sonları ile 12. yüzyıl başları yazıldığı sanılmaktadır. Zatü`l-Himme ile Battalname arasında konu benzerliği vardır. Ama Battalname`nin bu yapıtın doğrudan çevirisi ya da uyarlaması olmadığı iki metnin karşılaştırılmasından anlaşılmıştır.
Battalname`nin Türk halk öykülerinin geleneksel yapısı ve anlatım özelliklerine uymaması, onun Zatü`l-Himme`den ayrı (bugün kayıp) başka bir metnin çevirisi ya da uyarlaması olabileceği düşüncesini de güçlendirmektedir.
Battalname`deki olaylar da Zatü`l-Himme`de olduğu gibi Malatya ve çevresinde geçer. 8. yüzyıldaki Arap - Bizans savaşlarını, 9. yüzyılda Malatya`da kurulan Arap emirliğinin Bizans ordularıyla yaptığı savaşları, 10. yüzyıl ve 11. yüzyıldaki bazı tarihsel olayları da içine alan ve bunları Battal Gazi`ye mal eden Battalname, İslam dininin Anadolu`da yayılışı ile ilgili ilginç izler taşımaktadır.
Öyküde anlatıldığı biçimiyle Battal Gazi üstün nitelikleri olan, güçlü, zeki, bilgili ve usta bir savaşçıdır. Muhammed tükrüğünü, ona ulaştırılmak üzere bayraktarı Abdülvehhab Gazi`ye emanet etmiş, o da bunu uzun yıllar saklayarak Battal Gazi`ye ulaştırmıştır. Bu yolla her dili konuşan, üstün yetenekler kazanan Battal Gazi, keşiş kılığına girerek Hristiyanlar arasında rahat rahat dolaşır.
İslam dinini yaymak için savaşan Battal Gazi`ye ayrıca Dahhak, Rüstem ve Hamza gibi eski ve ünlü savaşçıların silahları da ulaştırılmıştır.
Battalname`de ve bugün Anadolu halkı arasında dolaşan menkıbelerde Battal Gazi, 12. yüzyılda Malatya yöresinde de egemen olan Danişmentlilerin sınır boylarındaki savaşlarda yiğitlikler gösteren bir kahraman olarak betimlenmiştir.
Battalname`nin düzyazı ve manzum olmak üzere birçok yazması bulunmaktadır. Bunlardan en eskisi 1436 - 1437 tarihli düzyazı metindir. Bilinen tek manzum Battalname ise 18. yüzyıl divan şairlerinden Darendeli Katipzade Bakayi (ö. 1785) tarafından kaleme alınmıştır. 1769 - 1770`te yazılmış bu yapıt 7 bin beyitten oluşmaktadır. Battalname, Menakıb-ı Gazavat-ı Sultan Seyyid Battal Gazi (1870, 6 cilt; yb Seyyid Battal Gazi, 1966 - 1970, 6 kitap, yay. haz. M. Faruk Gürtunca) adıyla basılmıştır. Hasan Köksal`ın konula ilgili Battalnamelerde Tip ve Motif Yapısı (1984) adlı bir incelemesi vardır.