Many biological tissues feature a heterogeneous network of fibers whose tensile and bending rigidity contribute substantially to these tissues' elastic properties. Rigidity percolation has emerged as an important paradigm for relating these filamentous tissues' mechanics to the concentrations of their constituents. Past studies have generally considered tuning of networks by spatially homogeneous variation in concentration, while ignoring structural correlation. We introduce here a model in which dilute fiber networks are built in a correlated manner that produces alternating sparse and dense regions. Our simulations indicate that structural correlation consistently allows tissues to attain rigidity with less material. We further find that the percolation threshold varies nonmonotonically with the degree of correlation, such that it decreases with moderate correlation and once more increases for high correlation. We explain the eventual reentrance in the dependence of the rigidity percolation threshold on correlation as the consequence of large, stiff clusters that are too poorly coupled to transmit forces across the network. Our study offers deeper understanding of how spatial heterogeneity may enable tissues to robustly adapt to different mechanical contexts. © 2022 authors. Published by the American Physical Society. Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.