In a 0–0 draw against Heart of Midlothian on 24 November 2012, Randolph caught Hearts' Callum Paterson's head with his leg as he challenged for a high ball; no card was issued, leading Hearts' manager John McGlynn to describe Randolph as a "lucky man". A few days later, the Scottish Football Association charged Randolph with "violent conduct by kicking an opposing player" and offered a two-match ban; Motherwell appealed, but the ban was upheld. Together with teammates Shaun Hutchinson, Nicky Law and Michael Higdon, Randolph was named in the 2012–13 PFA Scotland Team of the Year. Motherwell finished the season in second place behind Celtic, so qualified for Europe for the second year running.