After joining Crystal Palace's Academy at the age of 7, John spent the following 9 years at the South London club.
Bostock made his league debut on 29 October 2007 at the age of 15 years and 287 days, playing 20 minutes as a substitute in a 2–0 defeat to Watford at Selhurst Park, making him Palace’s youngest ever player. He also became the youngest ever Palace player to start a game, aged 15 years and 295 days, on 6 November 2007 against Cardiff City at Ninian Park. During his time at the South London club he represented England Under-16's and captained England at Under-17 level.
On 30 May 2008, Tottenham Hotspur announced the signing of Bostock on their club website. Crystal Palace later issued a statement denying reports that an agreement had been reached with Tottenham. Tottenham and Crystal Palace entered negotiations over the transfer fee, but an agreement could not be reached, leading to the sum being decided at a tribunal. On 9 July the tribunal declared that Tottenham would pay £700,000 for Bostock, with add-on payments of up to £1.25m dependent on appearances and a further £200,000 should he make his full international debut. A sell-on clause entitled Crystal Palace to 15% of any profit Tottenham would make from any future sale of Bostock.
Bostock made his first team debut for Spurs in an 8–0 pre-season win over Spanish side Tavernes, John providing the cross for Aaron Lennon‘s opening goal. On 6 November 2008 John made his competitive match debut in the 2008 UEFA Cup game against Dinamo Zagreb, coming on as a substitute and becoming the youngest player ever to play for Spurs at 16 years, 295 days, just beating the previous record-holder Ally Dick by six days. Bostock made a further two appearances in the Uefa Cup that season, however his career with Tottenham stalled after that and he had to wait until January 2012 for his next appearance, in an FA Cup match against Cheltenham Town.