Completed late August of 2001 as the fourth Badawi album, „Soldier of Midian“ was titled after a sacred warrior who could never be owned by man. The majority of the record was inspired by the following excerpt:
... And they said to him, come join us and fight for our God. I cannot, he replied, for it is you who wants me to fight, not our God. He lowered his sword and they raised theirs. If not for your God then for your people. How can I? He replied, for they have not told me to fight, only you have. They became angry but did not strike. If you do not join us then you will join the fate of our enemies. The winds grew stronger and he replied, How can I join your army when all I have is your word? I cannot worship the man, only the life of the man, If there is to be war let the horses decide who will be victorious. And even after a path has been paved, even then ...I will only follow the storm.
The recording is composed mostly in 3/4 and consists mainly of percussion and flute which are played by Raz as well as bass played by Shahzad Ismaily, and a dulcimer played by Carolyn HoneyChild Coleman. The instruments were then sampled, reconstructed, and remixed electronically.