The pair first met at Minami Aoyama Shōjo Kagekidan (南青山少女歌劇団, South Aoyama Female Opera Group, also called Nanshō), a stage group for teenage girls where Kajiura wrote music for some of the plays and Nanri was a performer.
Their first recording was "Akatsuki no Kuruma" (暁の車, Wheel of Dawn), an insert song in the popular mecha anime Mobile Suit Gundam SEED, though their debut single was the opening of Madlax, "Hitomi no Kakera" (瞳の欠片, Fragments of the Eyes), released on May 8, 2004.
In November of that same year, they released the opening theme for Sunrise's Bakumatsu Kikansetsu Irohanihoheto, "Kōya Ruten" (荒野流転, Wilderness Vicissitudes).
El Cazador de la Bruja was produced by Bee Train, whose anime productions FictionJunction Yuuka has also done songs for previously.
FictionJunction Yuuka performed alongside her fellow FJ peers in Yuki Kajiura LIVE Vol.