Einar Gerhardsen was born in the municipality of Asker, in the county of Akershus. His parents were Gerhard Olsen (1867–1949) and Emma Hansen (1872–1949). His father was rodemester in Public Roads Administration and was foreman of a trade union committee - fanekomiteen for Veivesenets arbeiderforening, and during Gerhardsen's childhood the trade union's leader Carl Jørgensen frequently visited their home, and sometimes they would sing The Internationale and "Seieren følger våre faner".
In 1932 he married Werna Julie Koren Christie (1912–1970), daughter of agent Johan Werner Koren Christie and Klara Rønning. The married couple had two sons, Truls and Rune and a daughter Torgunn. His brother was Rolf Gerhardsen and with him Einar Gerhardsen also had a lifelong working relationship. From the age of 17, Gerhardsen went to meetings in the Labour party's youth movement. In 1918, during the Finnish Civil War, Gerhardsen resigned his membership in the Church of Norway after the church sided with the "Whites" against the "Reds".
Originally a road worker, Gerhardsen became politically active in the socialist labour movement during the 1920s. He was convicted several times of taking part in subversive activities until he, along with the rest of the Labour party, gradually moved from communism to democratic socialism. He participated in the Left Communist Youth League's military strike action of 1924. He was convicted for assisting in this crime and sentenced to 75 days of prison.
By the middle of the 1930s Labour was a major force on the national political scene, becoming the party of government under prime minister Johan Nygaardsvold from 1935 until the German invasion in 1940. Gerhardsen was elected to Oslo city council in 1932 and became deputy mayor in 1938. He was deputy leader of the Labour Party from 1939.
After the German occupation of Norway in 1940, Gerhardsen became acting chairman of the Labour Party, as the chairman, Oscar Torp had gone into exile. Gerhardsen became mayor of Oslo on 15 August 1940, but was forced to resign by the Germans on 26 August the same year. In September, the occupation government banned all parliamentary political parties, including the Labour party.
During World War II, Gerhardsen took part in the organised resistance against the German occupation of Norway, and was arrested on 11 September 1941. Having already been under suspicion for a long time, Gerhardsen had been detained and subjected to interrogations on 31 previous occasions since the summer of 1940. Initially he was sent to Grini concentration camp in Norway. In February 1942 he was accused of leading resistance work from his imprisonment, and removed from the camp for interrogation. Initially interrogated at the police station at Møllergata 19, he was soon transferred to the Gestapo headquarters at Victoria Terrasse. At Victoria Terrasse he was tortured to reveal information on the resistance, but did not break. In April 1942 he was sent to Sachsenhausen concentration camp in Germany. In September 1944 he was transferred back to Grini, where he spent the rest of the war.
After the war, Gerhardsen formed the interim government which sat from the end of the occupation in May 1945 until the elections held in October the same year. The elections gave Labour an absolute majority in Parliament, the Storting, which it retained until 1961. Gerhardsen served as President of the Storting from 10 January 1954 to 22 January 1955.