The increasing importance of the walleye (Sander vitreus) fishery in the New River, Virginia, and recent research findings showing persistence of a presumptive native stock motivated a seven-year program of hatchery-based restoration of the native fishery. Candidate spawners were collected from spawning areas, and DNA from fin clips was genotyped at two microsatellite loci. Candidates exhibiting alleles at the Svi17 and Svi33 loci that characterize the presumptive native stock were spawned. Their young were reared at one of four fish hatcheries in Virginia and West Virginia. Approximately 600,000 fry and 800,000 fingerlings were stocked in riverine sections of the New River in Virginia and West Virginia. Since stocking began, ages 0-3 walleye have become much more abundant at the upper New River spawning areas. Catch rates in spring electrofishing samples have increased from 3 to 17 fish per hour in Virginia and from 1.2 to 26.6 fish per hour in West Virginia. Walleye catch per net-night from fall gill net sets in Claytor Lake, Virginia increased from 0.2 in 2001 to 3.1 in 2006. Comparison of data from creel surveys in 2002 and 2007 showed increasing angler effort directed toward walleye from 10% to 30% and increasing catch. Native walleye allele frequencies increased from 16% and 14% at the two marker loci in the 1997 to 1999 genetic surveys to 46% and 58% in the 2004 to 2006 surveys.