The 33-year-old provided the final pass for Thomas Müller to give the hosts an early lead against the World Cup finalists before Klose scored his 63rd goal for Germany leaving him just five short of Gerd Müller's all-time record.
The Lazio striker then set up Real Madrid's Mesut Özil to enjoy a simple tap in on 66 minutes as Germany lay down a marker for June's Euro 2012 over their neighbours.
This was Germany's first win over the Dutch since 1996 and will be seen as revenge for their 2-1 semi-final defeat in the 1988 European Championships when Marco van Basten's late winner broke German hearts – also in Hamburg.
At least one Dutch flag here, bearing the date 21-06-88, alluded to that defeat.
Dutch coach Bert van Marwijk had made four changes to the side which had been held to a goalless draw by Switzerland on Friday in Amsterdam.
Robin van Persie was replaced by striker Klaas-Jan Huntelaar up front, while Kevin Strootman came in for thigh injury-victim Rafael van der Vaart in midfield.
Right-back Khalid Gregory van der Wiel took over from Khalid Boulahrouz while AC Milan's Mark van Bommel replaced Nigel de Jong in midfield.
Germany coach Joachim Löw abandoned the experimental 3-4-1-2 formation which had resulted in Friday's 3-3 draw with the Ukraine in Kiev, for the familiar 4-2-3-1 with Klose as captain, playing as the lone striker and Mario Gomez on the bench.
This was Löw's 75th international as coach and his 52nd win, as Germany closed the year with a second major scalp after also beating Brazil in a friendly in August, and finished their Euro 2012 qualifying campaign with 10 wins from 10.
Klose, making his 113th appearance, showed the knee injury, which had kept him out of Friday's draw in Kiev, was behind him with his first shot in the first minute, then provided the pass for the first goal.
A Toni Kroos cross from the wing was squared by Klose for Müller to come onto the ball at pace to put Germany ahead on 15 minutes and his near-post shot gave Dutch goalkeeper Maarten Stekelenburg no chance.
The pair combined again when a superb run from Müller ended with a deft pass to Özil and with plenty of space, the Real Madrid star supplied a pin-point cross for Klose to head home on 26 minutes.
The Dutch barely had a look-in during the first 45 minutes and both Inter Milan's Wesley Sneijder and Klose picked up first-half bookings.
Klose then produced his second assist of the game when Müller's clever pass split the Dutch defence and he drew Stekelenburg for Özil to tap the ball into an empty net on 66 minutes to wrap up the win.