History of Visakhapatnam district goes back to an era of long dynastic rule. There is a story behind the name of the district. Tradition has it that some centuries ago a King of Andhra Dynasty encamped on the site of the present Head Quarters Town of Visakhapatnam on his pilgrimage to Varanasi and being pleased with the place, had built a shrine in honour of his family deity called Visakeswara to the South of the Lawsons Bay from which the district has derived its name as Visakheswarapuram which subsequently changed to Visakhapatnam. The encroachment of waves and currents of the sea supposed to have swept away the shrine into off shore area.

Inscriptions found here indicate that the district was originally a part of Kalinga Kingdom. It later went on to be conquered by the rulers of the Eastern Chalukya dynasty sometime in the 7th century AD. They established their stronghold here and ruled over it with their headquarters at Vengi. Following the Chalukyas, the region came under the rule of a number of rulers belonging to different dynasties. These include the Reddy Rajahs of Kondaveedu, the Gajapathis of Orissa, the Nawabs of Golconda and the Mughal Emperor Aurangzeb through a Subedar.

Due to the constant succession dispute among the Andhra Kings, the territory passed on to the French, and the region finally came under the British reign. There were no geographical graftings till 1936. It was in the same year when, consequent to the formation of the Orissa state, the Taluks namely Bissiom, Cuttack, Jayapore, Koraput, Malkanagiri, Naurangapur, Pottangi and Ryagada in their entirety and parts of Gunpur, Paduva and Parvathipur Taluks were transferred to Orissa State. The Visakhapatnam District was reconstituted with the remaining area and residuary portions of Ganjam District namely Sompeta, Tekkali and Srikakulam Taluks in entirety and portion of Parlakimidi, Ichchapuram, Berahmpur retained in Madras presidency. With the passage of time, the reconstituted District was found administratively unwieldy and therefore it was bifurcated into Srikakulam and Visakhapatnam districts in the year 1950. The residuary district of Visakhapatnam was further bifurcated and the Taluks of Vizianagaram, Gajapathinagaram, Srungavarapukota and a portion of Bheemunipatnam Taluk were transferred to the newly created Vizianagaram District in the year 1979.