In the summer of 1976, David Bowie and his companion Iggy Pop set out to make a new career in a new town. Two years later, Bowie had completed five great albums, reinventing himself and his previously washed-up friend Iggy in the process. The unique atmosphere of Berlin – bohemian but unpretentious, threadbare but glamorous – transformed the very sound of pop music. We can still hear its effects today in the work of Lady Gaga or Arcade Fire. Berlin life also rescued Bowie from a personal tailspin: "It was the first time in years that I had felt a joy of life and a great feeling of release and healing," he later said. "It's a city that's so easy to 'get lost' in – and to 'find' oneself, too." But today, the city that inspired one of Britain's greatest musicians is undergoing its own reinvention.
When Bowie moved to the city 35 years ago, seeking to escape the personal and pharmaceutical maelstrom of Los Angeles, he settled in the undistinguished area of Schöneberg, noted mainly as the setting for Christopher Isherwood's Goodbye to Berlin. Today, Schöneberg is still permeated with that bohemian, bargain atmosphere. My hotel, the Schöneberg, is simple and cheap, much like Bowie's old Altbau period apartment a few doors down at Hauptstrasse 155, a wide yet quiet main street. A quick espresso at Bowie's regular haunt, Neues Ufer – a basic, unpretentious mainly gay café with a photo of Bowie in the corner – gives that authentic, European, teeth-grinding caffeine rush, before I spend the morning in Bowie and Iggy's usual fashion – walking around and browsing the dozens of local junk, art and bookstores, many of them with displays that spill out on to the wide pavements around Nollendorfplatz and Winterfeldplatz.
On a sunny day, there's a fair number of people in the many bars and cafés, but the place still feels like a student backwater – like Bloomsbury or Fitzrovia 20 years ago, before soaring London property prices airbrushed away so much urban quirkiness. But no location in the UK contains anything as monumental as the huge, concrete air-raid shelter at Pallasstrasse, the street just around the corner where Goebbels gave his infamous "total war" speech. The bunker proved impervious to post-war demolition – so a block of steel-and-glass postwar apartments simply straddles it, as if it were an ancient rocky outcrop.
It's one of many disconcerting historical juxtapositions; many of which inspired Bowie back then. He loved the city for its state of post-war ruin – and for the echoes of its vibrant, Weimar past, when young men, as Isherwood described, would whistle up to the windows of the tall apartment buildings in search of girls – or boys. For Schöneberg had a vibrant gay community, who were among the Nazis' first victims, a fact commemorated in a plaque at Nollendorfplatz U-Bahn station.
Klaus Krüger, who back in the Seventies played drums with Tangerine Dream, is still in town. In the main, he says, Bowie had come "just to socialise in the way normal people do". Krüger used to hang out with Bowie and Iggy – both dressed down, in jeans, T-shirts, with cropped hair – and the artist Martin Kippenberger at clubs like the Dschungel, or The Unlimited on Kurfürstendamm. Both clubs are gone, as are the tanks that Bowie's producer Tony Visconti remembers rolling down the Ku'Damm in a demonstration of Nato firepower. Kreuzberg's Café Exil was another haunt, where they spent many happy hours "hang[ing] with the intellectuals and beats," said Bowie. "In the back they had this smoky room with a billiard table and it was sort of like another living room except the company was always changing."
Today the billiard table is gone, and the Exil is a pretty decent restaurant, the Horváth. This part of Kreuzberg – cobbled streets, tall trees bordering the Landwehr Kanal – is more placid than in Bowie's day, still a hangout for artists and musicians, although many of Berlin's young guns these days have headed East. Still, the laidback atmosphere that Bowie cherished is easily recognisable. "It was one of the few cities where I could move around in virtual anonymity," he said. "I was going broke; it was cheap to live. For some reason, Berliners just didn't care. Well, not about an English rock singer anyway."
In the same way that the old West Berlin was marooned as an island of capitalism inside communist East German territory, today many of its old hotspots are quiet. There's no better example than Hansa Tonstudio, where Bowie finished Low and recorded "Heroes", two albums whose electronic grooves were influential beyond measure. "Nothing else sounded like those albums. Nothing else came close," said Bowie. "They are my DNA." When Bowie first arrived at the studio Hansa looked wrecked, pock-marked with shell-holes, most of its windows bricked up. Today, its classical façade is pristine; but the main building is deserted, and my footsteps echo on the gleaming parquet of its Edwardian interior.
Once up on the first floor, I pull open the heavy mahogany door of the main room – it's dark inside, but I can make out the huge space where Bowie sang "Heroes", his voice filling the wood-floored interior. Today, this floor is empty, used mainly for private functions. Upstairs on the second floor, a smaller studio (where Iggy and David recorded "The Passenger", Iggy's ode to Berlin's S-Bahn system) survives. I'm treated to a look around, and breathe in that familiar, recording-studio atmosphere – cigarettes, stale beer, the electric smell of old-fashioned tape machines.
An intrinsic part of the atmosphere in which Bowie, Iggy and Brian Eno worked has gone; for in 1976 the studio control room was overlooked by a guard tower on the Berlin Wall. East German sentries toting sub-machine guns could look directly in, their presence suggesting to participants like Tony Visconti that "you shouldn't be making a record here". Now the Wall has gone, a wistful sense of loss remains. As Iggy Pop says today, "The Wall was beautiful. It created a wonderful island, the same way that volcanoes create islands in the sea."
A few other parts of the city retain their 1970s feel – most notably the Brücke museum, devoted to the Dresden Expressionist painters led by Ernst Kirchner and Erich Heckel. It was one of David's favourite haunts. It takes a leisurely bus ride to get there, through quiet, leafy, residential streets; the museum is tiny, a jewel-like, airy concrete box. Rather like Peggy Guggenheim's Venice gallery, it feels as if you're in a minimally sumptuous living room, except it's quieter, with just the odd, polite student absorbing the art. The works, by Heckel, Kirchner, Emil Nolde and others are intense, deep, often disturbing, paint and emotions splattered thickly on the canvases (Bowie copied the look on the covers of "Heroes" and Iggy's The Idiot.) But the setting is calm, a little oasis in time and space.
Outside of the Brücke, though, Berlin has moved on. Back in 1976, David took new visitors on a trawl around pre-war Tischtelefon bars – 1930s Bakelite telephones on each table allowed club patrons to flirt anonymously and make random assignations; now they've disappeared, along with their elderly clientele. The old, sleazy nightclub scene has gone up-market: the Kleine Nachtrevue on Kurfürstenstrasse is the nearest you'll get to the decadent old days, with its burlesque dancers and transvestite revues, but the entrance fee is a distinctly modern €30.
Even Bowie's favourite hotel, Grunewald's Gerhus – a rambling old Baroque warren hated by his American musicians, who found it creepy – has had a Karl Lagerfeld makeover and is now called the Schlosshotel. It's still beautiful, but is now respectable – and a little uptight. I recognise the emotion that Bowie described of his time in Berlin, "a sense of yearning for a future that we all knew would never come to pass".
Ironically, it's the old East Berlin – which Bowie could only visit briefly – that best evokes the West Berlin he loved. One example is the old Postbahnhof, an abandoned, utilitarian train station set in a fast-changing, post-industrial landscape in the old East, beside one of the longest surviving stretches of the Berlin Wall.
It turns out that the most definitive Bowie Berlin site is in a place that was off-limits to him. Throughout his time in the city David immersed himself in the work of Bertholt Brecht – an EP of Brecht songs would be his swansong in Hansa, and Berlin.
I stroll East with my friend Ed, an American writer who moved to the former communist part of the city in search of cheap rent. "When they divided up Berlin in 1945, the Russian commissars knew and kept the best parts – including this house," he tells me, as we wander down Chausseestrasse to a grey, stone-fronted building where Brecht lived in the 1950s. In the tiny, wood-panelled cellar we eat simple dishes of zander and pork knuckle, prepared from recipes collected by Brecht's wife, Helene Weigel, washed down with several bottles of Schwarzbier.
Later I walk to the nearby U-Bahn station. Mitte, the new centre, pristine by day, at night becomes a red-light district where women coo at tourists, much as in Christopher Isherwood's day. David Bowie would appreciate how sleaziness, airbrushed out of one location, pops up somewhere else. However much they gentrify, Berlin bleibt doch Berlin: "Berlin is still Berlin".
'Starman: David Bowie' by Paul Trynka is out this week (Sphere, £20).
Travel essentials: Berlin
* East Berlin's Schönefeld airport is served by easyJet (0871 244 2366; easyjet.com) from Bristol, Gatwick, Glasgow, Liverpool and Luton; Germanwings (0870 252 1250; germanwings.com) from Edinburgh and Stansted; and Ryanair (0871 246 0000; ryanair.com) from East Midlands, Edinburgh and Stansted. Other airlines, including British Airways and BMI, serve Tegel airport in former West Berlin.
* The Schöneberg Hotel, Hauptstrasse 135 (0049 30 780 9660; hotel-schoeneberg.de). Doubles start at €55, room only.
* Schlosshotel, Brahmsstrasse 10 (0049 30 895 840; schlosshotelberlin.com). Doubles start at €239, room only.
Eating and drinking there
* Neues Ufer Café Bar, Hauptstrasse 157 (00 49 30 7895 7900; ufer.de).
* Restaurant Horváth, Paul-Lincke-Ufer 44A (00 49 30 6128 9992; restaurant-horvath.de).
* Fritz Music Tours (00 49 30 3087 5633; musictours-berlin.com) offers bus and walking trips daily to key music locations in Berlin, plus tours around Hansa Studios. From €19 per person.