The sold-out, nearly three-hour show took in Fab Four favourites, hits from his later band Wings, solo efforts and a few new numbers and drew a warm, enthusiastic welcome from an audience spanning three generations.
"I'm so happy to be back in Hamburg where it all began 49 years ago," 67-year-old McCartney, one of the two surviving Beatles, told cheering fans in German.
Showing off a renowned knack for thrilling a crowd and remarkable endurance - he took no breaks during the marathon set, not even for a sip of water - McCartney offered moving tributes to his late wife Linda and the two dead Beatles John Lennon and George Harrison.
"I wrote this song for Linda but tonight it's for all lovers," he said, again in German using cue cards, before launching into his ballad "My Love."
He later played his 2001 single "Here Today" dedicated to Lennon, led the crowd in a rousing version of Lennon's "Give Peace a Chance" and did a sped-up rendition of Harrison's "Something" on a ukulele the singer gave him before he died of lung cancer in 2001.
McCartney also mucked it up for laughs. When he whipped off his black jacket to reveal a white shirt with black braces underneath, he quipped: "That is the big wardrobe change of the night - Madonna, eat your heart out!"
And he appeared tickled when the crowd jumped with a start at a massive on-stage fireworks display during "Live and Let Die," then clutched his chest, faking a heart attack.
McCartney's Good Evening Europe tour will see seven stops in five countries including a Christmas gig in London on December 22.
It follows sold-out concerts at US stadiums earlier this year and comes ahead of the release of a live album, "Good Evening New York City," recorded at the city's former Shea Stadium, where the Beatles played to an ecstatic crowd in 1965.
The northern German port city of Hamburg nurtured the Beatles as young performers in its seedy red-light district, long before they would become superstars, and now hosts a Beatlemania museum.
The show was McCartney's first in Hamburg since 2003 and came ahead of the 50th anniversary of the first Beatles gig in Germany when the unknown band from the English city of Liverpool played at a moth-eaten strip joint called the Indra Club on August 17, 1960.
He told a German newspaper recently that Hamburg was the city where the band earned its chops, playing night after night for more than two years.
"The city opened our eyes," he told the Frankfurter Rundschau. "We went there as children and came back as... old children. On the Reeperbahn we quite quickly had our baptism of fire when it came to sex – it was like we were let off our leashes. It was a wild time."
Klaus Voormann, who befriended the young Beatles in Hamburg in 1960 when he was an art student and later designed the cover of the "Revolver" album, said it was clear from the start that the band would be big.
"They would do anything for an audience, and in particular Paul," said Voormann, now 71, whom McCartney greeted from the stage.
"I think there is a breed of people that can't stop, and I think Paul is one of them. I really appreciate that," he said. "With some people I think, 'Why the hell are they carrying on? Just stop.' But with some (like Paul) I want them to carry on until they drop."