Born in Sutton-in-Ashfield, Nottinghamshire, Baptiste came up through the youth team at Mansfield Town. He was originally a central midfielder before gradually dropping back into defence and made his first-team debut aged 17 against Barnsley in April 2003. On 12 December 2003 he joined newly promoted Conference National side Tamworth on a one-month loan deal, making four league appearances, before returning to Mansfield on 12 January 2004. On 7 February he was sent out again on loan for a month, this time to Burton Albion, for whom he made three appearances. Baptiste established himself as first-choice central defender for Mansfield Town towards the end of the 2003–04 season. He was ever-present during the 2006–07 season, and by the end of the campaign had made over 150 appearances for Mansfield. Baptiste signed a new three-year contract despite interest from Crewe Alexandrain the summer of 2007. However, he missed three months of the 2007–08 season with a back injury. After Mansfield Town were relegated to the Conference National at the end of the 2007–08 season, he requested a transfer, which was granted. He made a total of 198 appearances for the club in all competitions, scoring six goals.
Blackpool
On 1 July 2008, Baptiste agreed a deal to join Championship club Blackpool. Speaking about the move, he described it as a "great opportunity and challenge". He started the season as a regular in the Seasiders reserve team, and for the first few months of the season he was not named in the first-team squad. He made his first-team debut on 22 November 2008 against Wolverhampton Wanderers at Molineux at right-back. He scored his first goal for the Seasiders in a 1–1 draw with Ipswich Town at Portman Road on 14 February 2009. Three days later he was named in the Football League's "Championship Team of the Week". Baptiste cemented his place in the starting line up in the latter stages of the 2008–09 season, playing either centre back or right back. On 20 January 2010, after 27 appearances and two goals in the 2009–10 season, Baptiste signed a new two-and-a-half-year contract until June 2013. He said of the new contract: "I am very pleased. I had a good chat with the gaffer and Thommo and the direction of the club is upwards and I want to be a part of it." Blackpool manager Ian Holloway expressed his belief that Baptiste can play in the Premier League: "Baps has played at left-back, right-back and centre-back and he has been different class. I believe he can play in the Premiership and I have told him that. I am working on the areas that he needs working on, but as a defender I don't think I have had a better one and I am delighted he has signed." On 14 August 2010 he scored as Blackpool marked their Premier League debut on the opening day of the 2010–11 season with a 4–0 win over Wigan Athletic at the DW Stadium. Baptiste scored the final goal of the game. He was subsequently named in the Premier League "Team of the Week", alongside teammate Marlon Harewood. Baptiste played in the Championship play-off final against West Ham United in May 2012, which was won by West Ham 2–1. After the match Baptiste was vocal in his criticism of West Ham's style of football saying "They just hoof it, and hope for the best".
In May 2013, Baptiste signed a three-year deal with fellow Championship side Bolton Wanderers on a free transfer that took effect once his Blackpool contract expired on 30 June 2013. He made his debut for Bolton in their 1–1 draw with Lancashire rivals Burnley on 3 August 2013, operating in the right-back position. He recorded his first goal for Wanderers in the same month by scoring a consolation in the 4–1 away defeat at Blackburn Rovers. His first goal at the Reebok Stadium was Bolton's opener in their 2–2 draw against Derby County in an end to end game which saw Wanderers claim a share of the spoils. Baptiste joined Blackburn on loan. He scored his first goal against Nottingham Forest. He scored his second goal for the club against Sheffield Wednesday.
On 6 July 2015, Baptiste joined Middlesbrough. On 11 July, Baptiste suffered a suspected double leg fracture, 20 minutes into a pre-season match against York City. On 1 March 2016, Baptiste signed for Sheffield United on loan. On 31 August 2016, Baptiste signed for Preston North End on a season-long loan. He scored his first goal for the club in a 2–2 draw with Birmingham City on 27 September 2016.
On 7 August 2017, Baptiste joined Queens Park Rangers on a free transfer. On 31 January 2019, Baptiste joined Luton Town on a loan deal until the end of the 2018–19 season.
Doncaster Rovers
On 2 August 2019, Baptiste signed for Doncaster Rovers on a one year contract. After only two matches he suffered an Achilles injury.. He proceeded to miss the rest of the season through injury.
