He grew up kicking a tennis ball in White City, Jabavu in Soweto. His talent blossomed at Morris Isaacson High School where he started playing for Jomo Cosmos juniors. His parents did not believe that he could make a living from playing football because they knew it is a short career but they encouraged him, his first pair of soccer boots were Puma SE Rangers that his parents bought for him.
His younger brother Ruben is a soccer player. He lives in Fourways, Johannesburg. “Life in the suburbs is somewhat lonely. Everyone minds his own business. You hardly ever see neighbours chatting over the fence. “I miss the feeling that exists in the townships of being a member of one big family. Asking for a loan of sugar, washing powder or salt from the neighbour when your own runs out,” he said.
Nicknamed "Yeye","Modimo wa bolo (God of football) and "Beyoncé" Letsholonyane mainly played in the lower leagues until joining Jomo Cosmos in 2006. Two years later he signed with Kaizer Chiefs under Muhsin Ertugral where he has since been an integral part of the line-up despite regularly battling injuries. Letsholonyane made his debut alongside Gordon Gilbert on 30 August 2008 in a 2–1 loss against Thanda Royal Zulu. He came close to scoring as he took a powerful shot outside the box but crashed onto the crossbar. Letsholonyane scored the winning penalty in the 2008 MTN 8 final and Chiefs won 4–3 over Mamelodi Sundowns. He got his first call-up after the final. He missed most of the 2011/12 season after picking up a knee injury on international duty, and only got featured in just 13 league matches for Chiefs. In the 2012-13 season during Chiefs' league and cup double triumph he played 26 league matches and scored 3 goals. Halfway through the 2013-14 season, Letsholonyane's career nearly ended against Lamontville Golden Arrows when his leg was hacked inwards, he came off and was replaced by Josta Dladla, Chiefs won 1-0. He only strained and damaged his ligaments and was ruled out for the last game of the year against AmaZulu on 22 December 2013. He scored in the MTN8 quarter final against Mpumalanga Black Aces in the 2nd minute in a 4-0 win and was voted Man of the Match. Letsholonyane scored his first league goal of 2014–15 in a 2–1 win over Mpumalanga Black Aces. He scored in the MTN8 2nd leg semi-final against Platinum Stars in the 57th minute to give Chiefs a 4–0 aggregate lead on 24 August 2014, he won his second Man of the Match of the tournament. Letsholonyane scored in a 2–0 win over Platinum Stars on 27 August 2014. He scored a brace against University of Pretoria on 13 September 2014 in a 2–1 win. He scored an equaliser in a 1–1 draw against Moroka Swallows on 22 October 2014.