A commonly overlooked aspect of conservation planning assessments is that wildlife managers are increasingly focused on habitats that contain non-native species. We examine this management challenge in the Gila River basin (150,730 km2), and present a new planning strategy for fish conservation. By applying a hierarchical prioritization algorithm to >850,000 fish records in 27,181 sub-watersheds we first identified high priority areas (PAs) termed “preservation PAs” with high native fish richness and low non-native richness; these represent traditional conservation targets. Second, we identified “restoration PAs” with high native fish richness that also contained high numbers of non-native species; these represent less traditional conservation targets. The top 10 % of preservation and restoration PAs contained common native species (e.g., Catostomus clarkii, desert sucker; Catostomus insignis, Sonora sucker) in addition to native species with limited distributions (i.e., Xyrauchen texanus, razorback sucker; Oncorhynchus gilae apache, Apache trout). The top preservation and restoration PAs overlapped by 42 %, indicating areas with high native fish richness range from minimally to highly invaded. Areas exclusively identified as restoration PAs also encompassed a greater percentage of native species ranges than would be expected by the random addition of an equivalent basin area. Restoration PAs identified an additional 19.0 and 26.6 % of the total ranges of two federally endangered species—Meda fulgida (spikedace) and Gila intermedia (Gila chub), respectively, compared to top preservation PAs alone—despite adding only 5.8 % of basin area. We contend that in addition to preservation PAs, restoration PAs are well suited for complementary management activities benefiting native fishes.