Native American artifacts were recovered in various locations on Government Island. The largest concentration of artifacts was found overlooking Aquia Creek. a rare Clovis projectile point was found, indicating the Paleoindians were present in this area prior to 8000 B.C. Paleoindians likely operated out of temporary camps located near high-quality stone supplies and areas plentiful with game where they carved their points and tools, as well as hunted and gathered food.
Other recovered artifacts, including Madison and Levanna projectile points and Townsend ceramic shards, indicate that Native Americans were present in this area between 1200 B.C. and A.D. 1600.
In 1608, European explorer Captain John Smith mapped the Potomac River and its tributaries and negotiated trade with the Patawomeck Indians who were prevalent in this area. Smith traveled up Aquia Creek, noting it as Quiyough (kwee' yuh), Algonquin for "Gulls." He referred to "Quiyough" twice in his papers, once when describing the creek and again when naming the Indian village on its south side.