Abstract: We provide a computational framework for approximating a class of structured matrices (e.g., block Toeplitz, block banded). Our approach is to map the structured matrix to tensors, use tensor compression algorithms, and map the compressed tensors back to obtain two different matrix representations: the sum of Kronecker products and the block low-rank format. The use of tensor decompositions enables us to uncover latent structure in the problem and lead to computationally efficient algorithms. The resulting matrix approximations are memory efficient and easy to compute with, and they preserve the error due to the tensor compression in the Frobenius norm. While our framework is quite general, we illustrate the potential of our method on structured matrices from three applications: system identification, space-time covariance matrices, and image deblurring.