Latar Cerita Black Order The Earl of Millenium, musuh bebuyutan manusia yang paling awal, pernah muncul di awal zaman untuk menghancurkan dunia. Untuk menghalaunya, beberapa orang bekerja sama membuat Innocence—sebuah substansi yang mampu menghancurkan tentara-tentara buatan The Earl—dan menjadikan mereka sebagai para pelopor Innocence. Dengan Innocence, The Earl pun akhirnya dapat dikalahkan, namun dunia hancur dalam proses (tiga hari kegelapan, masa-masa
The Great Flood sekitar 7000 tahun silam).
Dengan hilangnya The Earl dan Akuma-akuma-nya, dunia pun kembali damai. Meski demikian, ada sebuah ramalan bahwa The Earl akan kembali suatu saat nanti, bersama dengan kehancuran dunia. Oleh karena itu, para pelopor ini meninggalkan sebuah instruksi untuk menggunakan Innocence. Semua ini ditinggalkan dalam bentuk kubus yang ditemukan di pesisir Yunani Selatan, sekitar abad ke-13. Kubus ini ditemukan oleh pihak gereja dan disimpan di Vatikan.
Tahun 1401 (abad ke-15), keberadaan The Earl mulai terdeteksi. Banyak beberapa saksi yang selamat dari serangan Akuma melaporkan kejadian ini pada pihak gereja. Vatikan yang mendengar hal ini pun membuka kembali seksi “Black Order” sebagai lembaga militer pihak gereja untuk menghabisi The Earl beserta tentaranya. Pada awalnya, pembentukan dari Black Order sendiri memiliki kendala tersendiri, karena Innocence tersebar ke penjuru dunia akibat banjir besar sementara Black Order tidak memiliki alat-alat untuk mendeteksi Innocence secara menyeluruh. Alhasil, Black Order lebih sering kewalahan menghadapi serangan The Earl.
Sekitar pertengahan abad ke-17, aktivitas The Earl tampak mengendur akan sesuatu. Pada saat yang sama, banyak masyarakat mulai meninggalkan kepercayaan mereka dan berpaling kepada sistem harta. Kesenjangan sosial di berbagai tempat meningkat tajam, akibat keberadaan pemberontakan dan ketidakpuasan beberapa pihak. Tanpa diketahui Black Order, The Earl diam-diam berada di belakang semua fenomena ini dan perlahan—namun pasti—menambah pasukannya.
Dengan mulainya kekacauan di berbagai belahan penjuru dunia sementara The Earl of Millenium seakan sudah menjadi masalah yang telah lalu, keberadaan Black Order menjadi sebuah pertanyaan besar. Meskipun mayoritas penganut ajarannya percaya bahwa The Earl hanya bersembunyi, banyak dari anggota institusi itu sendiri yang mulai kehilangan rasa percaya, hingga akhirnya melepaskan diri dari organisasi—atau setidaknya, tidak aktif kembali dalam organisasi.
Imperialisme subur di berbagai daerah. Beberapa di antara para Imperialis tersebut menggunakan nama agama sebagai salah satu alasan untuk menjajah dan mengambil sumber daya alam daerah jajahan. Banyak bangsa yang hidup dalam opresi bangsa lain, sementara bangsa imperialis menikmati hasil penindasan. Tindakan ini tidak lepas dari hasutan The Earl melalui para
broker-broker-nya, yang ternyata bertindak diam-diam di balik layar. Di masa penuh penindasan dan opresi ini, keaktifan Black Order sudah menurun jauh.
Banyak anggota Black Order yang keluar dari ajaran dan segera menghilang—sebuah sinyal merah yang menandakan bahwa ada sebuah gerakan mencurigakan yang mencoba untuk menghancurkan Black Order. Vatican Central hanya melihat masalah ini sebelah mata, karena bagi mereka siapapun yang sudah mengkhianati kepercayaan pantas mendapat hukuman yang setimpal.
Segalanya kembali terbuka, dengan kemunculan Earl yang kembali tiba-tiba pada abad ke-19 (1800). Black Order yang sudah mengalami penurunan kekuatan kembali kelabakan karena kemunculan yang mendadak ini. Kekacauan banyak terjadi; bahkan banyak para ‘mantan’ Exorcist yang menjadi incaran. Kebanyakan dari mereka tewas, namun dengan Innocence yang mampu diambil kembali sebelum jatuh ke tangan Earl. Sementara itu, metode penyegelan kekuatan Innocence pada suatu wadah untuk menutupi jejak Innocence itu sendiri belum ditemukan. Tempat bersarangnya Innocence cenderung menjadi lokasi yang rawan; inilah salah satu alasan mengapa Black Order selalu dalam bahaya yang kontinu. Setidaknya sampai tahun 1860-lah baru ditemukan metode penyimpanan Innocence yang lebih efektif. Theodora Xena selaku akomodator Innocence Guardian mampu menutup jejak Innocence dari endusan The Earl.
Meskipun sudah lebih dari satu dekade mencari, Black Order belum menemukan Innocence kunci,
The Heart—sebuah Innocence yang menjadi sumber asal usul dari Innocence lain yang jika dihancurkan, Innocence lain pun turut hancur. Pihak The Earl of Millenium dan Black Order pun berlomba—kedua pihak dikejar waktu, karena siapapun yang paling cepat mendapatkannya memiliki kunci kemenangan di tangan mereka.
Are you in or not, Exorcist?