Before the English sailed into the Chesapeake Bay and named the Elizabeth River, there was a Native American settlement there. The Chesapeakes apparently were not subjugated or allied with Powhatan, though the reports by the leaders in the early days of Jamestown are contradictory.
In 1585, the Roanoke Colony settlers may have visited the Elizabeth River or Nansemond River watersheds. Those colonists then abandoned their attempt to settle permanently on the barrier islands, but leaders of the next effort planned to start anew on the south shore of the Chesapeake Bay.
Of course, that last batch of English colonists had their plans changed. In 1587 their ship captain dumped them back at Roanoke Island again, in order to have more time to attack Spanish ships. (Captains got a share of the profits in any Spanish shipping they could capture.)
There is speculation that the English in "lost colony" ended up, willingly or unwillingly, with Chesapeakes. Powhatan destroyed tribe around time arrived at Jamestown, and claimed to have remainder of Roanoke process, but no independent evidence residue - such as a collection iron tools weapons was even seen.
Powhatan may have "planted" his own town at the original homeland of the Chesapeakes, after destroying them in 1607-08. There was plenty of protein in the brackish waters to support a large town there, and Powhatan knew he had to secure the fringes of his paramount chiefdoom (the area he controlled) while he coped with the intrusion of an alien people in the center of it.

Norfolk is the premier port city in Virginia. It's shipments surpass those from Newport News, Richmond's Deepwater Terminal, and small ports throughout the Tidewater region. The deep channel and harbor protected from storms attracted commecial shipping and then a British naval repair yard prior to the American Revolution.
However, the Norfolk Naval Shipyard is actually in Portsmouth - unlike the Norfolk Naval Station. According to its official history, it's the oldest naval shipyard in the United States. It was started by the British in 1767, leased by the United States government in 1794, and purchased in 1801.
In 1794-99 the USS Chesapeake was built in the yard. It was severely damaged off Cape Henry in 1807, while sailing to the Mediterranean and unprepared for a fight. The British warship, the HMS Leopard, impressed a few "deserters" in an incident that helped start the War of 1812.
In 1861, the Federal forces burned ships and destroyed the shipyard before abandoning it at the start of the Civil War. The Confederates then raised the USS Merrimack and converted it into the ironclad CSS Virginia. The new warship had one day of uncontested control of Hampton Roads, before the Federal ironclad USS Monitor fought the CSS Virginia to a standstill. The Confederates blocked the Union navy from supporting General McClellan's march up the Peninsula. Closing the James River via the CSS Virginia (plus the fortifications at Drewry's Bluff) may have prevented a quick end to the war. The Confederates abandoned Norfolk and destroyed the Gosport Navy Yard in March, 1862.
Why is the shipyard where it is? The Elizabeth River offers one of the world's deepest natural harbors. It is sheltered from storms, yet close to the Atlantic Ocean - with a clear channel for military and civilian traffic. There are lots of names and dates associated with the shipyard, but a consistent thread throughout all the history: Norfolk was not a great place for a military base or civilian city until the end of the French and Indian War. At that time, the British Navy had clear naval superiority on the high seas, comparable to the global supremacy exerted by the United States today.
Even then, the site had its downsides. The British at the start of 1776, the rebellious American colonists soon thereafter, the Yankees in 1861, and the Confederates in 1862 all recognized the port was not defensible. They destroyed Norfolk rather than defended it. The British knew they could not defend it against land attack, while the colonial rebels knew they could not defend it against British Navy attack from the sea. The Yankees had the same concern as the British - and the Confederates had a tiny navy, so they used the same logic as the colonists 85 years earlier.
The naval yard was known as Gosport until 1862, when it was renamed after Norfolk. Note that no one - British, Americans, or Confederates - ever named the naval yard after Portsmouth...
Today, the Norfolk Naval Shipyard claims to be "one of the largest shipyards in the world specializing in repairing, overhauling and modernizing ships and submarines. It's the oldest and largest industrial facility that belongs to the U.S. Navy, and it's also the most multifaceted..."