Celtic, so qualified for Europe for the second year running. Birmingham City With Randolph's contract due to expire at the end of the season, Motherwell manager Stuart McCall said in mid-April that there was only a "slim possibility" of keeping him at the club. On 10 May 2013, McCall confirmed that Randolph would be leaving, and four days later, English Championship club Birmingham City announced that Randolph would join them on a free transfer once his Motherwell contract expired. He signed a two-year contract to commence on 1 July. He went straight into the starting eleven, made his debut in a 1–0 defeat at home to Watford on 3 August, and remained ever-present in Championship matches throughout the season, though Colin Doyle played in all Birmingham's cup ties. The unbroken run continued into the next season, until Randolph was sent off late in the home defeat to Bolton Wanderers on 18 October 2014 for bringing down Craig Davies (who missed the ensuing penalty), so was suspended for the next match. He was ever-present in league matches for what remained of the season, and also made his first cup appearance for the club, in the FA Cup fourth-round defeat by West Bromwich Albion. Manager Gary Rowett said that had a Premier League club made a bid for Randolph's services in the January transfer window, he would not have stopped him leaving, but he wanted to keep him at Birmingham. The club confirmed in May that he had rejected the offer of a contract extension, and would leave as a free agent under the Bosman ruling at the end of his existing deal. West Ham United On 30 May 2015, West Ham United confirmed that Randolph would join the club on 1 July when his contract with Birmingham expired. He made his debut on 2 July in a 3–0 victory over Lusitanos in a Europa League qualifying match. Randolph made his league debut for West Ham in a 4–3 home defeat to AFC Bournemouth on 22 August 2015. He continued in goal, and kept a clean sheet in a 3–0 win against Liverpool on 29 August which was West Ham's first league win at Anfield since 1963. Randolph played in West Ham's last three matches of the 2015–16 season which included their final match at the Boleyn Ground, a 3–2 victory over Manchester United. He played in 15 matches in all competitions