In 1892, the community in which Navy School is now located was called Thompson's Corner. This community was to receive a post office, but because a post office in Louisa County, Virginia, already bore the name Thompson, the Post Office Department insisted that the residents of Thompson's Corner choose a different name.
Prospective patrons submitted numerous choices, but all were rejected because they too were in use elsewhere. At the residents' request the Post Office Department sent a list of permissible names. All of the names were very short - most contained only two or three letters. Because "Navy" was one of the few longer names on the list, the community voted to so name its post office. Although the post office was closed in 1905, the area unofficially kept the name.
The original school was built in 1888 and took the name "Navy" after the post office was established. The existing school was built between 1955 and 1956. Additions were made in 1959, 1978, 1986, and 2004.
In past years, Navy School's symbols have been an anchor and Captain Ness (Navy Elementary School Students). In 1985 students selected the dolphin as the school's mascot.