Increasing disturbance frequency and severity on coral reefs has caused declines in the abundance of structurally complex corals and many fish species that depend on them. However, most studies have focused on the shallowest 10 m, despite coral habitat extending to >30 m in many regions. Reefs in deeper water and offshore locations are less exposed to many stressors associated with coral decline, and may offer a refuge for coral-associated fishes. Understanding how distributions and species-specific fish−habitat relationships vary along depth and distance-from-shore gradients is critical for assessing refuge potential. Here we examined the community structure, distributions and coral habitat associations of 123 reef fish species along a depth gradient from <1 to 40 m, from coastal to offshore reefs in Kimbe Bay, Papua New Guinea. Overall fish density and species richness declined with increasing depth but increased with distance offshore, such that deep offshore assemblages supported similar richness to shallow inshore sites. The most distinctive fish assemblage occurred at depths <1 m and ~25% of species were observed in only the shallowest 5 m. However, ~60% of species occurred at or below 20 m and 24% were broadly distributed from <1 to 30 m, with depth ranges of many species increasing with distance offshore. Strong relationships between fish abundance and coral habitat were observed, and 85% of species that were strongly associated with coral occurred at depths ≥20 m. Our results suggest that while many species are restricted to vulnerable shallow depths, deep offshore reefs provide a potential refuge for a substantial proportion of coral-associated fishes threatened by degradation of shallow coastal reefs, and deep reefs should be afforded greater consideration in conservation planning for coral reef fishes.