Erdogan is expected to run for the presidency in August, and Germany - with a Turkish community of three million, about half of them eligible voters - would be a strong constituency for the controversial leader.
Erdogan and his Islamic-rooted Justice and Development Party (AKP) have polarized Turks at home and abroad over what critics call his authoritarian style, a crackdown on civil liberties and corruption scandals under his rule.
In the western city of Cologne, where Erdogan spoke in an 18,000-seat arena, protesters waved banners that read: "Erdogan persona non grata", "Resistance against AKP fascism" and "Corruption, sharia, sultanate - Erdogan, you are not a democrat".
"Taksim is everywhere, the resistance is everywhere," the protesters chanted, a week before the anniversary of Istanbul's Gezi Park and Taksim Square anti-government protests that ended in harsh police crackdowns.
Many demonstrators wore hardhats with the word "Soma" on them, the western Turkish town where 301 coal miners died this month in the country's worst ever industrial disaster that sparked renewed street rallies.
Erdogan outraged many with his apparent indifference to the tragedy when he remarked that mining accidents are in "the nature of the business", and after photos showed his advisor Yusuf Erkel kicking a protester in Soma.
Amid the heightened passions, police in Germany made several arrests after breaking up a scuffle between security staff guarding the venue of Erdogan's speech and his opponents.
Rally organizers from the Turkish Alevi community, which follows a moderate form of Islam, said as many as 65,000 people had joined the rally, while authorities put the attendance at 40,000.
The mood was very different on the other side of the river Rhine. Erdogan followers arrived at the 18,000-seat Lanxess Arena, which was festooned with Turkish flags and a banner that read "Welcome Mr Prime Minister, we are proud of you".
Conservative supporters, including many men in suits and women wearing traditional headscarves, passed through airport-style security as speakers started hailing the invited speaker.
To Erdogan's loyal supporters, he is a strong leader who rose from a poor Istanbul neighbourhood to oversee over a decade of economic growth, raise Turkey's stature in the region and make his mark with a series of eye-catching megaprojects.
"The arrival of Erdogan divides Turks living here in Germany," said Ufuk Cakir, president of the Association of Alevis of North Rhine-Westphalia state, which was co-organizing the protests.
Speaking at the demonstration, Cakir told AFP that "the recent events in Turkey, the corruption scandals, the killings of members of religious minorities, show ... yet again the need for our mobilization".
Erdogan's long-scheduled Germany visit has sparked controversy for days, and Chancellor Angela Merkel this week urged the premier to show "a sense of responsibility and sensitivity" while there.
Top-selling daily Bild in an open letter referred to Erdogan's recent controversial policies, such as blocking Twitter and YouTube, and wrote: "Erdogan, you're not welcome here! ... We do not want politicians like you."
Cologne mayor Juergen Roters said "this election stop by the Turkish prime minister is a provocation", while the head of the Association of German Turks, Safter Cinar, told AFP he hoped Erdogan would strike a "conciliatory tone".
Erdogan's speech was officially to mark the 10th anniversary of the AKP's sister organisation in Germany, the UETD, but was widely seen as a campaign rally.
In August presidential elections, in which Erdogan is expected to run, some 2.6 million overseas Turks will be allowed to vote abroad for the first time - including about 1.5 million in Germany.