Mathenge was educated at Strathmore School, He rose to fame in 1999 through a star-search contest on Kenya's urban music station 98.4 Capital FM, which he won with his original song "Megarider." The song was about a penniless young man who is trying to seduce a woman but only has enough money for Kenya Bus tickets, and not the rich lifestyle she desires. He later recorded the track with producer Tedd Josiah and it went on to be hot on the charts for weeks. This was the turning point in his musical career. He went on to sign with the Ogopa Deejays label in 2001 and collaborated with artists such as the late E-Sir on "Boomba Train," and Amani on the regional hit "Ninanoki" in 2002 which broke Kenyan chart records by remaining nearly four months at number one.
He is regarded as one of modern music pioneers in Kenya alongside his wife Wahu kagwi.
He has gone on to tour across the East African region and in the U.S.A and U.K. In 2004, he released his debut album On Fire. In 2004, Mathenge married Ogopa Deejays label mate Wahu Kagwi. They have two daughters, Tumiso who was born in 2006, and Nyakio born in 2013. He is also an architect and graduated from the University of Nairobi.
South African pop group Jamali's wildly popular song "Maisha" was the subject of so much controversy with allegations that Jamali had stolen the song from Nameless. The dispute was settled when Jamali released their CD/DVD of Yours Fatally and credited Nameless as one of the writers of "Maisha".
Nameless has been featured in a song with the Kansoul, " moto wa kuotea mbali" which has received favourable reviews.
- 2004 Kisima Music Awards - Best Boomba Pop Artist
- 2006 Kisima Music Awards - Best Male Artist, Best Afro Fusion & Best Music Video (Sinzia).
- 2006 Pearl of Africa Music Awards (PAM Awards) - Best Male (Kenya)
- 2007 Tanzania Music Awards - Best East African Single (Sinzia).
- 2007 Channel O Music Video Awards - Best Male Video (“Sinzia”) 
- 2008 Pearl of Africa Music Awards - Best Kenyan Male Artist 
- 2008 Kisima Music Awards - Male Artist of the Year & Best Video ("Salari")
- 2009 Tanzania Music Awards - Best East African Single ("Salari") 
- 2009 MTV Africa Music Awards - Artist of The Year, Best Male & Listener's Choice 
- 2004 Kora Awards - Best African Group (Nameless & Mr. Lenny) 
- 2005 Tanzania Music Awards - Best East African Album ("On Fire")
- 2006 MTV Europe Music Awards 2006 - Best African Act
- 2006 Channel O Music Video Awards - Best East African video ("Juju" featuring Mr. Lenny) 
- 2009 MTV Africa Music Awards - Best Performer 
- "Unique learning that nurtures discipline and talent". Standardmedia.co.ke. 2011-06-14. Retrieved 2011-08-04.[permanent dead link]
- The Standard, August 21, 2007: 100 most influential Kenyans
- The Standard, August 21, 2007: 100 most influential Kenyans - Entertainment
- Kisima Awards winners 2006
- Ugandaonline.net: PAM Awards 2006 Winners
- Tanzania Music Awards: 2007 winners
- Museke: Channel O Music Video Awards 2007 winners
- Museke: PAM Awards Winners 2008
- Kisima Music Awards: 2008 Kisima Music Awards winners
- Daily Nation, Buzz Magazine, April 12, 2009: The Kilimanjaro Awards 2009:The highs and lows
- Museke: MTV Africa Music Awards (MAMAs) 2009 winners
- Yeahbo.net, Kora Wards 2004 Archived 2005-01-06 at the Wayback Machine.
- Tanzania Music Awards - Nominees 2005
- africa.bizcommunity.com: Channel O Award nominees released
- Museke: MTV Africa Music Awards (MAMAs) 2009 nominees