Before Nate and Greg met, Nate was the DJ for deadpoetsociety, a hip hop group based out of Indianapolis. The group consisted of three members, Nate Corrona (DJ Dust), Michael Porter (Rahlo), and Joel Wilson (Thin King), and performed at various venues in and around Indianapolis and the Mid-West from 1995 to 1999. In 1998, Nate attended a hip hop conference in Florida and met Greg Owens, who was at the time an MC for The Pride, living in Atlanta. Greg was then asked to be a part of deadpoetsociety and subsequently toured with the group until around the end of 1999. At that point, Joel had left the group to return to his home in England, and the three current members all decided to change the group name because, as Greg mentioned in an interview, "there [are] a lot of Dead Poets Society's around.". Nate then decided to move to Atlanta, feeling that the group would have better opportunities in that city, musically and ministry-wise. Michael chose to stay in Indianapolis and soon afterward began his own group, The BackSoil Project.
The name "Mars Ill" is a shortened version of Mars Hill, mentioned in Acts in the Bible, (Acts 17:19). "ILL" is capitalized for clarity, as it's often mistaken for the Roman number 3, or "iii".
The group's first album was called Raw Material, released on Sphere of Hip Hop Records, in early 2000. It was considered a success in the underground hip-hop movement, garnering rave reviews from both secular and Christian critics alike. In 2002, Uprok Records (a child label of Tooth & Nail Records) offered to re-release the album. With this release, a few track changes were made: Under the Sun and The End from the Sphere of Hip Hop release were replaced with Sphere of Hip Hop (original), Fade to Black, and The Abolition of Manchild.
Following the 2003 release of Backbreakanomics, Dust and Manchild began work on a new album titled ProPain with a 2004 release date. As excitement built for the new album, EMI executives began to get involved to the project which they planned to release as a major Gotee Records release. However, on review of the track line-up, they discovered that certain tracks had uncleared samples, and they put the project on hold until further notice. As Dust worked to clear the samples on some tracks and modify others, the release date was continually pushed back. To ease fans' disappointment and frustration, the group released Pirate Radio, showing their resilience through this trial. ProPain's legal issues continued, however, and anticipation mounted through a premature release and recall, and several re-releases of previous albums. The waiting finally paid off in May 2006 when the CD finally came out shy a few tracks of the original, but with new songs to help complete the project. Lead singles included: "More" featuring Ahmad of 4th Avenue Jones and Anthony David, and the revolution-minded "Sound Off".