We quantified native fish densities along a depth-temperature gradient within a temperate-tropical marine transition zone (North Carolina continental shelf) to examine the role of depth and temperature in structuring these communities. We also examined the distribution of invasive lionfish (Pterois volitans, P. miles) to evaluate a laboratory-derived thermal minimum for lionfish. We collected year-round continuous bottom water temperature data from 2000 to 2010 and surveyed lionfish (2004 to 2010), conspicuous fishes (2006 to 2010) and cryptic smaller-bodied fishes (2007 to 2010) at depths from 5 to 46 m using SCUBA. Bottom water temperatures were constant across the depth gradient during summer and increased from inshore to offshore during winter. The conspicuous fish community was structured by 3 depth zones, 5–14, 15–37 and 38–46 m, that corresponded with winter mean temperatures of 13.9, 17.9 and 20.9°C, respectively. The cryptic fish community was structured by 4 depth zones, 5–15, 18–24, 27–38.5 and 39.5–46 m, with corresponding winter mean bottom temperatures of 13.8, 15.6, 18.7 and 20.9°C. In contrast, summer temperatures were not important in structuring either the conspicuous or the cryptic fish community. Thus, fish communities in the spring/summer appear to be structured by the pattern of bottom water temperature experienced the previous winter, supporting previous studies that indicate winter minimum temperature is important for determining fish distribution and abundance in temperate marine ecosystems. In addition, the deeper fish communities were dominated by tropical species. Lionfish, a tropical species, was found in the highest densities from 38 to 46 m and present in locations with a winter mean of 15.3°C and higher. Increasing temperatures could favor a potential expansion of invasive lionfish and native tropical species into the nearshore waters on the North Carolina shelf, resulting in unforeseen community structure and trophic disruptions.