The army originated from the White Sea Air Defence Corps of the Northern Military District (Soviet Union), which was commanded by twice Hero of the Soviet Union General-major Pyotr Pokryshev: To cover the European North in 1958 on the basis of the White Sea Air Defence Corps, the Northern Air Defence Army was formed in accordance with a directive of the General Staff of the Air Defence Forces dated June 17, 1958.
The new army included: In 1959 a Guards air defence artillery regiment was incorporated into the Northern Air Defence Corps; subsequently, the anti-aircraft missile brigade (Peninsula)]).
In 1960, an air defence missile regiment (upgraded into a brigade) was relocated from the Odessa Air Defence Corps to the Arkhangelsk Region with its control point in Mirny.
To strengthen fighter aviation, the 524th Fighter Aviation Regiment was transferred from the Air Force of the Northern Fleet, reequipped with the Yak-25, and relocated to Letneozersky Plesetsk District.
Subordinate formations were also assigned combined-arms numbers: Around 1965, the 359th Independent Transport Aviation Regiment, Military Unit Number 28064, was formed at Vaskovo Airport, Arkhangelsk Oblast, and joined the Army.