Selve konstruktionen af muren begyndte den 13. august 1961.

Efter 2. verdenskrig var resterne af Tyskland delt op i fire zoner: den amerikanske, den britiske og den franske zone samt den sovjetiske zone. Fra 1947 blev Tyskland opdelt i to dele (reelt fire, men de vestlige dele samarbejdede). I de tre vestlige zoner oprettedes i 1949 staten BRD (Bundesrepublik Deutschland) og samme år oprettedes i den sovjetiske zone staten DDR (Deutsche Demokratische Republik). DDR lå mod nordøst og BRD mod vest og syd. Problemet omkring samarbejdet mellem de forskellige besættelseszoner opstod allerede kort tid efter 2. verdenskrigs afslutning. Med indførelsen af D-Marken i de vestlige besættelseszoner sammen med beslutningen om at oprette en vesttysk nation blev fjendskabet mellem Sovjetunionen og de vestallierede tydeligt. Fra 1948-1949 forsøgte Sovjetunionen forgæves at tvinge de allierede til at forlade Berlin ved en blokade af Vestberlin.

Nikita Khrusjtjov rettede 27. november 1958 et ultimatum til vestmagterne og krævede, at de skulle trække sig ud af Berlin, og at Øst- og Vestberlin skulle slås sammen til én by under DDR’s kontrol. Dette skulle opfyldes inden seks måneder, og hvis det ikke skete, ville Sovjetunionen slutte separat fredsaftale med DDR og overlade al sovjetisk kontrol til kommunistpartiet i DDR. Dette skulle ske for at hindre den massive flugt af (oftest unge og uddannede) tyskere fra DDR til Vesttyskland, noget som bevirkede, at DDR var ved at kollapse økonomisk. 3,12 millioner tyskere havde siden 1949 fundet vejen fra DDR til Vesttyskland.

Før Berlinmuren blev bygget, var der ikke restriktioner på rejser mellem Øst- og Vestberlin (i modsætning til rejser mellem DDR og Vesttyskland), og tyskere i DDR, som ønskede at komme til Vesten, kunne rejse direkte ind i Vestberlin for så at flygte til Vesttyskland. Det var desuden ikke usædvanligt, at tyskere bosat i DDR arbejdede i Vestberlin. Østberlin havde derfor besvær med at besætte 45.000 arbejdspladser.