Rhodes attended Baldwin High School in Milledgeville, Georgia and was a student and a three-year letterman in both football and basketball. In football, he was a Class 4A All-State selection. Rhodes graduated from Baldwin County High School in 1998. He played at Georgia Military College in 1999 and 2000, where he was an All American defensive-lineman. He also won the Golden Owl's Bowl in 1999. He signed with Valdosta State in 2000, playing two years. He was a two-time All Conference player and played in the Division II National Championship in 2002.
Rhodese signed with the B.C. Lion in April 2003. He played in the pre-season before being cut in week ten of the season. He went on to play two years in the National Football League Europe (NFLE). He was allocated by the Kansas City Chiefs with the Cologne Centuries in 2003 and the Berlin Thunder in 2004. He played in the World Bowl with the Thunder. He signed with the Miami Dolphins in 2005 and with the L.A. Avengers (AFL) in December 2005. He played two years with the Avengers, leading the team in sacks and forced fumbles in his rookie year. He played with the Columbus Detroyers in 2009. He went back to school in 2012 and graduated in December 2015 with a degree in criminal justice.