At Newcastle United he played alongside international footballers such as, Laurent Robert, Gary Speed, Alan Shearer, Shay Given, Nolberto Solano Patrick Kluivert and Kieron Dyer. In his first three seasons at Newcastle, Newcastle played in European football; twice in the Champions League, in seasons 2002–03, 2003–04 and twice in the UEFA Cup in seasons 2003–04 after failing at a group stage in the Champions League, and for the 2004–05 UEFA Cup his last season at Newcastle. Jenas also won 14 of his 21 caps for England when with Newcastle United. On 31 August 2005 at the age of 22, Newcastle United accepted an offer of £7 million from Tottenham Hotspur.