Adam Hjalmar Egede-Nissen was born on an Øvre Rinnan farm at Frol (today part of Levanger) in Nord-Trøndelag, where his father Paul Christian Egede-Nissen (1835–1891) was then serving in the medical corps of the Norwegian Army. Having qualified as a medical doctor in 1858 and having been active as a military physician in the Italian liberation struggle led by Giuseppe Garibaldi, by 1863 the father was practicing medicine in Tromsø; by 1867 he was a commissioned officer with the rank of major and was a regimental surgeon stationed with the army at Levanger. Adam Egede-Nissen's mother was Sophie Amalie Normann of Harstad (1826–1912), widow of Søren Schøning (1816–1861), who had been a merchant on Grøtøya in Kvaløya municipality; she married his father in 1863, and the couple had two children, Pauline Fayette Egede-Nissen (b. 1864) and Søren Kristian Henrik Egede-Nissen (b. 1866) before their last child, Adam Egede-Nissen, was born in 1868. Besides his two full siblings, he had a stepbrother, Jakob Schøning.
Adam Egede-Nissen graduated from Trondheim Cathedral School in 1886, receiving his Cand philol. (master's degree) two years later. In 1887 he was appointed as a post office assistant in Nordland county; and in 1890 as a mail clerk; he transferred in the following year to become a mail clerk in Bergen. He was postmaster in Vardø (in Finnmark near the Russian border) from 1897 to 1911, when he became postmaster in Stavanger. On 13 May 1899, during his time in Vardø, he founded the newspaper "Finnmarken"; he was its editor for many years.
Egede-Nissen was a member of the Vardø city council from 1903 to 1911. With Vardø being the easternmost town in Norway — and indeed in all of Western Europe — it formed a thriving duty-free centre for the Pomor trade of Norwegian pollock for Russian rye grain and other goods brought by merchants from Arkhangelsk. Making use of his contacts with Russian merchants and officials, Egede-Nissen was among the first Norwegians to establish working links with anti-Tsarist Russian groups. As early as 1902 he had begun printing and smuggling literature across the border into Russia promoting democracy and socialism. In 1906 he was a co-founder of Nordens Klippe, a decidedly socialist Norwegian mineworkers union.
In 1900 Egede-Nissen was first elected to the Storting, representing the Liberal Party for the Hammerfest-Vardø-Vadsø electoral area. During his first term in parliament, he was a member of the Standing Committee on Roads (1900–1903). During some of his time in parliament, fellow socialist Thorolf Bugge, who had worked in the Vardø post office with him since 1898, served as acting postmaster there (1901 to 1906).
Having been re-elected in 1903, Egede-Nissen broke with the Liberals in 1905 and joined the Labour Party in the Storting, becoming one of its leaders. He was re-elected for the Labour Party at the next two parliamentary elections in 1906 and 1909, representing the same constituency as before. From 1903 through 1912 he was a member of the Standing Committee on the Military, and during the years from 1906 to 1912 the Storting elected him as a member of the Lagting.
Egede-Nissen gained prominence during the August 1909 parliamentary debate on army reorganization, espousing the then radical ideas of neutrality and military disarmament.
From 1910 he served as one of nine members of a parliamentary alcohol commission which was mandated to chart Norway's future laws on the sale of wine, beer and distilled spirits. The Storting adopted their 1918 majority report, in which the commission recommended that all importation and sale of alcohol be conducted through controlled storehouses (samlag), the profits of which would flow to the Norwegian Treasury (Statskassen), whilst breweries and distilleries would remain privately owned — a position held by a six-member majority of the committee. Egede-Nissen and Sven Aarrestad, parliamentary leader of the Temperance Party (Avholdspartiet), however, contended that the government should restrict the legal sale of alcohol by allowing individual municipalities to vote to ban its local sale and set a goal of eventually achieving national prohibition, at least of distilled spirits, whilst a third dissenter, famed Norwegian physician and psychiatrist Johan Scharffenberg, supported an immediate total prohibition of all liquor sales, characterizing alcohol as "this nerve poison that turns people into animals."
Having become Stavanger's postmaster in 1911, he declined to stand for re-election in the 1912 election, especially as he would no longer be living in the electoral area that he had represented.
Egede-Nissen was elected to the Stavanger municipal council in 1913, and in 1915 he was elected mayor, a post he retained till 1919. After the Russian Revolution of 1917, though, Egede-Nissen became sympathetic to the Bolshevik cause. Having been elected to leadership of the labour Party in 1918, he went to the new Soviet Russia, where he met with Lenin and participated in a meeting that led to the establishment of the Comintern, although he did not attend the founding meeting in March 1919; the only Norwegian attending was Emil Stang, supposedly to represent the Norwegian Labour Party. The Soviets had invited the Labour Party to join the Communist International, a goal that Egede-Nissen shared, but his party eventually repudiated the principles of Lenin and remained social democratic.
During his mayoralty, Egede-Nissen was fined for his leading role in organizing a general strike held on 21 June 1919 in support of the Russian Revolution.
In 1921 he was once again elected to the Storting, this time representing Stavanger for the Labour Party. In 1923 the tensions could no longer be papered over, and the Labour Party formally split into two factions; the smaller group organized itself as the Communist Party of Norway, and Egede-Nissen become a founding member of the nascent Communist Party, serving as party chairman from 1934 to 1946; another Labour Party member who joined at this time was Peder Furubotn, who served as Communist Party chairman from 1925 to 1930. At their 1946 congress the party replaced Egede-Nissen with Emil Løvlien as chairman.
During the Nazi occupation of Norway in World War II, Egede-Nissen fled to Canada aboard a whaling ship. In Toronto he enlisted in the anti-Nazi struggle and was sent first to Reykjavík and later to New York City. The ship taking him to the U.S. was torpedoed, and although some sailors were killed, Egede-Nissen and many others were rescued by the crew of an American ship. In the autumn of 1944 he returned to Finnmark in northern Norway, where he participated in the struggle against Nazi occupation by serving as one of the translators for the Red Army, which had begun to drive the occupying German troops out of the country.
Egede-Nissen was married to Georga ("Goggi") Wilhelma Ellertsen (1871–1959); they had ten children, seven of which would become stage and film actors: Aud Egede-Nissen (1893–1974), Gerd Grieg (1895–1988), Ada Kramm (1899–1981), Oscar Egede-Nissen (1903–1976), Stig Egede-Nissen (1907–1988), Lill Egede-Nissen (1909–1962) and Gøril Havrevold (1914–1992).