Naldo made his Werder Bremen debut, starting the whole game, in a 5–2 win over Arminia Bielefeld in the opening game of the season. He played in both legs against Basel in the UEFA Champions League Qualifying Round, as the club advanced to the Group Stage following a 3–3 draw through away goal. Since joining Werder Bremen, Naldo quickly established himself in the starting eleven, playing in the centre–back position. His first goal for Werder Bremen came on 18 November 2005 against Wolfsburg, in a 6–1 win. However during a 2–1 loss against Schalke 04 on 26 November 2005, he suffered a shoulder injury that saw him missed one match. Naldo returned to the starting line–up against FC Köln on 11 December 2005 and scored his second goal of the season, from a from 30 meters free kick in a 4–1 win. Ten days later on 21 December 2005, he scored his third goal of the season, from a header in a 4–1 win against Hannover 96. Naldo then helped the club kept three consecutive clean sheets between 25 March 2006 and 8 April 2006, including a 3–0 win against Bayern Munich. Unfortunately, Werder Bremen ended up finishing second place behind Bayern Munich, but helped the club qualify for the UEFA Champions League next season. In his first season at Werder Bremen, he played in all but two of the club’s Bundesliga games and in seven of their eight Champions League fixtures, along with two appearances in Champions League Qualifiers, making a total of forty–five appearances and scoring three times in all competitions.