North Rhine Westphalia

[Yeahsayyeah]

The base of the CDU narrowed over time and the SPD was successfull filling the arising gaps for a long time. There are several factors, that seem to play a role. Of course, if you compare the SPD results of the forties/fifties and later years, bear in mind the self-castration and later ban of the KPD, that had their strongholds at Rhine and Ruhr and still got 14 percent in the 1947 Landtag election.

The SPD was for a long time underrepresented as its "natural base" were workers in a protestant environment. You still can spot the borders of the protestant Lippe region in electoral maps, today. The region that is now NRW was mostly catholic and even the protestant spots like the old towns of Dortmund or Essen where overwhelmed during industrialization by migration of catholics from all over the Rhineland, Silesia and (Congress) Poland.
The Centre Party then emerged as the party of a minority defined by religion (catholics) in a environment after the founding of the German Empire, that was hostile to them (Kulturkampf etc.), so it had appeal to catholic junckers, peasants, bourgeois and workers alike. So it was a catch-all-catholic-party with several wings and had overall reformist social policies (European meaning).
After the division of the SPD they lost the revolutionary types to the KPD so all they got was reformist seculars and Protestants (generalization alert).

You have to bear in mind that all three parties had their own societal organisations, e.g. trade unions. The Rhineland and Ruhr area was a heartland of the Christlicher Gewerkschaftsbund (Christian Trade Union Federation) in the Empire and Weimar years. After 1945 the DGB was founded as a general trade union organisation that united the socialist/social democrat "Free" and the Christian trade unions, who lost their millieu-defining role, though some remnants of these organisations still exist.
Also, the CDU was not the "catholic party" as the Zentrum was and catholics were not a minority anymore in the new Federal Republic. The Nazi era ironically also helped to loosen the bounds between church and people, especially in the urban areas, e.g. by crushing the remnants of the Polish millieu.
So catholic workers now were over time much less inclined to vote CDU based on religion and it seems to have been Adenauer's (from Rhineland, former mayor of Cologne) and Arnold's (long time prime minister, former mayor of Düsseldorf, to the left of Adenauer) personal appeal that delayed the results of this process for several years.

That the CDU abandoned the Christian left by favouring remilitarisation brought a bourgeois element to the SPD that surely set up the symbolic changes of the Bad Godesberg party program and helped to come out of their class tower. Long-term prime minister Johannes Rau, came from the GDP.

After 1966 the SPD was for a long time seen as successfull moderating the economic and social changes that came with the decline of the coal and steel industry. They were percieved as "Kümmererpartei" ("a party that takes care of"; much of the appeal of prime minister Hannelore Kraft comes from hat) and the CDU never had that much of an offer towards the urban working class, that has been struck by many crises for over 45 years. 

Migration after World War II also plays a role (Most of the expatriates and those who left GDR came from protestant areas). The so called "guest workers" and their offspring probably did not play an electorally role until the late 80s, but they were and are still, strongly leaning towards the parties of the left.