"Berliners are mourning a musical genius and one of their most famous fellow citizens," Berlin mayor Michael Müller wrote, adding that the city's connection with Bowie had not just been musical.
"He as an artist belonged to us," Müller added. "We are proud of that."
By 9:26am, people had already begun leaving candles and floral tributes outside the Hauptstrasse 155 block of flats in the Schöneberg district, where Bowie lived with Iggy Pop in the late 1970s while recording his "Berlin Trilogy" of albums.
By 3:25pm, the building was besieged with flowers - with one of the bouquets even playing Bowie's music to passers-by.
And the star's passing was front-page news on the online editions of all the capital's newspapers.
"David was the rare artist that truly searched for that 'whatever it is' until the end of his life – he held a torch high so others might see the paths and possibilities in the dark ahead," Anton Newcombe, lead singer of The Brian Jonestown Massacre and Berlin resident, told The Local.
"He brought great things out in others," Newcombe added, name checking Iggy Pop and Tony Visconti.
MESSAGE FROM IGGY: "David's friendship was the light of my life. I never met such a brilliant person. He was the best there is. - Iggy Pop"— Iggy Pop (@IggyPop) January 11, 2016
DON'T MISS: David Bowie's Berlin in pictures
"David provided a foundation to bring some of the most important music of our time – my time – into being."
Newcombe also pointed to "Heroes", Bowie's blockbuster collaboration with Brian Eno – which Bowie also sung in German as "Helden" – as his "finest hour".
Bowie sung it at a legendary concert in front of the Reichstag (parliament building) - then a deserted hulk abandoned for decades because of its proximity to the Berlin Wall - in 1987.
The song, released on the album of the same name in 1977, had become an instant hit with its lyrics referencing the Wall – and the hope that the people might one day overthrow it.
I, I can remember (I remember)
Standing, by the wall (by the wall)
And the guns shot above our heads
(over our heads)
And we kissed,
as though nothing could fall
(nothing could fall)
And the shame was on the other side
Oh we can beat them, for ever and ever
Then we could be Heroes,
just for one day
"'Heroes' is one of Bowie's best-known works and became an anthem for our still-divided city and its longing for freedom," Berlin mayor Müller said of the song.
"With this song, Bowie didn't just set an enduring bar for music, but also expressed irreversibly his connection to our city."
David Bowie talks about performing Heroes at the Berlin Wall pic.twitter.com/1JYTKy8tkX— Elena Cresci (@elenacresci) January 11, 2016
The German Foreign Ministry went so far as to say that Bowie's song "helped to bring down the Wall".
The Wall would be a theme Bowie returned to decades later with the release of "Where are we now" in 2013 – in which he sings of the Bösebrücke in northern Berlin, where the first checkpoint was opened in 1989.
The Local will be following the tributes to Bowie from Berlin throughout the day and updating this article – please check back.