Before Murray ever recorded an album, he traded verses with Big Daddy Kane under the name MC Do Damage. Later, he was introduced to Erick Sermon of EPMD by K-Solo. Sermon included Murray on his album No Pressure on the single "Hostile". His first album, The Most Beautifullest Thing in This World, was released in 1994 on Jive Records. The title track from this album remains Murray's biggest solo hit. This album was given 4 mics by The Source. Murray continued to enjoy a high media-profile by appearing on a Coca-Cola advertisement and guesting on remixes of Mary J. Blige’s ‘Be Happy’, Total’s ‘Can’t You See’ and LL Cool J’s ‘I Shot Ya’.
Murray's second album Enigma was released in 1996 on Jive. It received similar ratings from critics, but it was not quite as commercially successful as the previous album. Murray also appeared on Busta Rhymes' debut album The Coming, representing the Def Squad on the track "Flipmode Squad Meets Def Squad" along with Redman and Jamal. In 1998, The Def Squad covered "Rapper's Delight" by the Sugarhill Gang. They would later release their own album, El Niño. Murray's third album It's a Beautiful Thing was released in 1999. Murray also appeared on the song "Home Alone" by R. Kelly.
Def Jam released his He's Keith Murray in 2003, containing the single "Yeah, Yeah U Know It." This song has guest appearances from fellow Def Squad members Redman and Erick Sermon. Murray dedicated "Christina" to his sister. That same year, Murray was featured on the video game Def Jam Vendetta. Shortly after this, Murray was accused of choking two employees of Def Jam – although he said the confrontation was limited to words – and was subsequently dropped.
He released his fifth solo album Rap-Murr-Phobia on July 31, 2007. It debuted at number 52 on the U.S. Billboard 200 chart. The lead single was "Nobody Do It Better" featuring Tyrese and Junior.