A történet egy Madlax nevű fiatal lányról szól, aki titkos ügynökként dolgozik. A nevét nem tudja, emiatt használja a Madlax nevet. Küldetései alatt mindig meg akarja tudni, hogy ki volt az apja, de soha nem derül rá fény. Apját 12 éve vesztette el a Gazth-Sonika-i háborúban, rejtélyes körülmények között.
Eközben egy másik lány életét ismerhetjük meg, aki nem más mint Margaret Burton. Egy kedves, de igen érdekes lány. Nagyon furán gondolkodik, és sok minden jelentéktelen dolognál megakad, amiknél bizonyos emlékek jutnak eszébe. Margaret szintén 12 éve vesztette el az emlékezetét, és mikor megtalálták, csak annyit tudott mondani, hogy Madlax.
Mindezek mellett pedig egy Enfant nevü alvilági csoport végez különböző adat gyüjtéseket, amiket brutális módon hajtanak végre. De miért keveredik ebbe bele Madlax, mi köze Margarethez? Ezt majd megtudhatjátok.
A sorozat grafikája nagyon gyönyörű és szépen kidolgozott, emellett a zenéje is, és a története is teljesen magával ragadó. A cselekmények igazándiból a 7. rész fele kezdenek inkább elindulni, de érdemes addig megnézni.
Akinek tetszett a .hack//SIGN vagy a Noir, annak feltétlenül ajánlom, mert ez az anime is egy remek Bee Train-es darab lett.