Известность среди поклонников MMA получил благодаря выдающимся физическим данным и силе. Особенно фанатам запомнился бросок прогибом, исполненный Рэндлменом в поединке против Фёдора Емельяненко.
Рэндлмен начал заниматься вольной борьбой во время учёбы в Университете Огайо. Он дважды выиграл соревнования национальной ассоциации студенческого спорта по борьбе.
Рэндлмен участвовал в турнирах под эгидой Ultimate Fighting Championship как в тяжёлом, так и в полутяжёлом весах. В 1999 году после победы над Морисом Смитом Кевин получил право на титульный бой за звание чемпиона в тяжёлом весе. Однако по итогам пяти раундов он уступил Басу Руттену решением судей.
Руттен вскоре завершил карьеру, оставив титул вакантным. На него претендовали двое: Рэндлмен и Пит Уильямс. Бой между ними так же продлился пять раундов, однако, в отличие от поединка полугодовой давности, победу праздновал Рэндлмен.
В июне 2000 года Рэндлмен провёл первую защиту титула, победив решением бразильца Педро Риззо, однако следующий поединок лишил его чемпионства: вернувшийся в UFC Рэнди Кутюр нокаутировал Кевина в третьем раунде.
После этого поражения Рэндлмен перешёл в полутяжёлый вес и проиграл первый бой в новом дивизионе Чаку Лидделлу. Впрочем, в следующем поединке он реабилитировался перед болельщиками победой над Ренату Собралом.
В сентябре 2002 года Рэндлмен дебютировал в Pride Fighting Championships победой над японским борцом Митиёси Охарой. В 2002 году Рэндлмен одержал ещё две победы (обе нокаутом): над Кенити Ямамото и Мурило Руа. После этих побед Кевин стал претендовать на титульный бой с текущим обладателем пояса — Вандерлеем Силвой, однако руководство Pride решило сначала свести его с другим претендентом — Куинтоном Джексоном на Pride 25. На исходе седьмой минуты Джексон отправил оппонента в нокдаун точным ударом колена в солнечное сплетение и принялся добивать его, сидя сверху, тем самым вынудив рефери остановить бой.
За этим поражением последовала неудача в поединке с Кадзуси Сакурабой, после которого Рэндлмен снова набрал вес и перешёл в тяжёлый дивизион для участия в Гран-при 2004. В одной восьмой финала ему противостоял один из фаворитов турнира — хорват Мирко Филипович, которого Рэндлмен, однако, нокаутировал на второй минуте, что стало сенсацией того турнира.
В четвертьфинале Рэндлмену противостоял действующий чемпион Pride Фёдор Емельяненко. Во время борьбы в углу, Кевину удалось взять захват и провести эффектный бросок прогибом, буквально впечатав Фёдора головой в ринг. Однако развить успех американцу не удалось, и вскоре он сдался из-за проведённого Фёдором узла локтя.
После этого Рэндлмена настигла череда поражений. Через два месяца он проиграл Рону Уотерману, а в декабрьском турнире уступил Филиповичу. В апреле 2005 года вернувшийся в полутяжёлый вес Рэндлмен уступил Кадзухиро Накамуре.
В октябре 2006 года на Pride 32 Рэндлмен проиграл болевым приёмом бразильцу Маурисио Руа в своём последнем поединке в Pride.
После более, чем полуторагодичного перерыва, связанного с лечением почек и стафилококковой инфекции, Рэндлмен вернулся на ринг, одержав победу единогласным решением над Рё Кавамурой в мае 2008 года на турнире Sengoku 2, организованного World Victory Road. В дальнейшем планировался бой Кевина против американца Джеффа Монсона, однако Рэндлмен травмировал плечо и не смог принять участие в этом бою.
На ноябрьском Sengoku 6 американцу противостоял болгарин Станислав Недков. Оба бойца провели бой активно и много действовали как в стойке, так и в партере. По итогам трёх раундов раздельным решением победа была присуждена Недкову.
На пресс-конференции перед турниром Strikeforce: Shamrock vs. Diaz было объявлено о подписании Рэндлменом контракта с Strikeforce.
Дебют Кевина состоялся в июне 2009 года против Майка Уайтхеда на турнире Strikeforce: Lawler vs. Shields. Первые два раунда остались за Уайтхедом, который успешно проводил тейкдауны, которые, впрочем, никакого серьёзного урона Рэндлмену не принесли. В третьем раунде Кевин был вынужден начать более агрессивные действия для того, чтобы завершить поединок досрочно. Ему удалось отправить противника в нокдаун и обрушить на упавшего оппонента множество ударов, однако ни нокаутировать Уайтмена, ни принудить его к сдаче Рэндлмен не смог и проиграл судейским решением (29—28, 29—28, 29—28).
В мае 2010 года на турнире Strikeforce: Heavy Artillery Рэдлмен выступил в роли «гейткипера» (от англ. gate keeper — «хранитель врат») для Роджера Грейси, недавно подписавшего с организацией контракт. Их поединок завершился победой бразильца удушением сзади.
Таким образом, Рэндлмен проиграл 10 из 13 последних поединков.
Рэндлмен принял участие в нескольких реслинговых шоу. Первый раз он участвовал в вечере, проведённом японской организацией HUSTLE в январе 2004 года. А спустя пять лет — в феврале 2009 года — на шоу Absolute Wrestling Radio бросил вызов Кофи Кингстону из организации WWE.
В апреле 2009 года Рэндлмен сочетался браком со своей давней подругой Элизабет. У них двое детей: сын Келвин, занимающийся американским футболом и дочь Жасмин.