Black Elvis/Lost in Space is the fourth studio album by emcee Kool Keith, but recorded under the alias of Black Elvis. This is the first album performed under this alias. It was intended to be released the same day as First Come, First Served, but was pushed back by Columbia and ended up being released four months later through Relativity Entertainment Distribution rather than Sony Music Distribution, denoted by the WK prefix instead of the customary CK prefix and the legal copy on the release. Kool Keith uses very complex rhymes on various subject matters from Black Elvis' viewpoint on half of the album and on the other half elaborates on space travel and being lost in space. This is the first album for which Keith handled all of the production, although drum programming was done by Kutmasta Kurt and Marc Live.
A promotional video was made for the track "Livin' Astro" which aired on a few episodes of the MTV show Amp in early 2000. The video features Kool Keith acting as several different personas amidst a sci-fi backdrop that resembles the Black Elvis/Lost in Space album cover. The personas include the Original Black Elvis, Orange Man, the Kid in the Commercial, Lonnie Hendricks, and Light-Blue Cop.
Kool Keith was displeased with the lack of promotion for the Black Elvis project, and vented his frustrations about his label on the songs "Release Date" and "Test Press." He also published the e-mail addresses of several Ruffhouse executives, asking his fans to demand better promotion.