the last 32 of the UEFA Cup the following season, with Nolan's goal in the first round defeat of Lokomotiv Plovdiv helping the club reach the group stages. He scored the winner as the club overcame Zenit St. Petersburg 1–0 in the group stages, and a further nine in the league to help Bolton finish eighth, missing out on European qualification. The 2006–07 season saw Nolan take over from the departed Jay-Jay Okocha as club captain. His three league goals helped Bolton to again qualify for the UEFA Cup. Nolan's long throw-in set up a goal, which helped Bolton achieve a 2–2 draw away against German champions Bayern Munich, who dominated the match. Despite reaching the first knockout round, Bolton's league form suffered as they were pulled into a relegation fight, eventually finishing the season one point above the relegation zone in 16th. Nolan scored in the 2–0 win over Sunderland in May that virtually secured the club's Premier League status. Having made 323 league appearances for the club, in January 2009, Nolan began talks with representatives of Newcastle United over a move to the north-east club, following perceived criticism of his performances by some of the club's supporters. Newcastle United On 29 January 2009, it was revealed that Newcastle had agreed a £4 million fee with Bolton Wanderers, which was confirmed the next day, with Nolan travelling to Tyneside to discuss terms and undergo a medical. Nolan completed his move on the same day, signing a -year contract. On 22 February, Nolan received his first red card playing for Newcastle United in a home match against Everton for a two-footed foul on Victor Anichebe. At the end of the season, Newcastle were relegated to the English Championship. Nolan was noted as one of the more vocal Newcastle players over the summer, demanding an end to the off the field distractions at the club, and suggesting the club should be looking to acquire players for an immediate return to the Premier League. Nolan played a key role in Newcastle's push for promotion the following season; he scored his first league goal for Newcastle on 22 August against Crystal Palace, and the first hat-trick of his career, as part of a 4–0 away win against Ipswich Town on 26 September. Nolan captained Newcastle for the first time in a 5–1 win against Cardiff City taking over for the absent Nicky Butt