We introduce a new class of large structured random matrices characterized by four fundamental properties which we discuss. We prove that this class is stable under matrix-valued and pointwise non-linear operations. We then formulate an efficient method, based on an extremization problem, for computing the spectrum of subblocks of such large structured random matrices. We present different proofs -- combinatorial or algebraic -- of the validity of this method, which all have some connection with free probability. We illustrate this method with well known examples of unstructured matrices, including Haar randomly rotated matrices, as well as with the example of structured random matrices arising in the quantum symmetric simple exclusion process. tured random matrices arising in the quantum symmetric simple exclusion process.