New Alexandria, Virginia  New Alexandria is an unincorporated community in the census-designated place of Belle Haven, Fairfax County, Virginia. It comprises large homes, condominiums, and a major shopping center. New Alexandria was founded in 1892.