Carroll started his youth career in Newcastle United. He scored some goals for the reserve team. He made his first-team debut on 2 November 2006. He was 17 years and 300 days old then. This was in a 1–0 UEFA Cup win over Palermo. He came on as a late substitute for Nolberto Solano. In doing so, he became the youngest ever player to represent Newcastle in Europe.