We provide a computational framework for approximating a class of structured matrices; here, the term structure is very general. Our matrix-to-tensor invertible mapping allows us to pose the matrix-approximation problem as a tensor-approximation problem. Mapping the tensor approximant back to matrix space, we obtain a structured matrix approximation that can be expressed as a sum of structured Kronecker products, or in block low-rank form, or as a sum of mixed Kronecker and block structured matrices, depending on which tensor decomposition is employed. We illustrate the ability of our method to uncover latent structure in the operators that can be leveraged in large-scale computations and consider where our approach could benefit from randomization. This is joint work with Arvind Saibaba (NCSU).