We consider non-Hermitian random matrices X∈C^n×n with general decaying correlations between their entries. For large n, the empirical spectral distribution is well approximated by a deterministic density, expressed in terms of the solution to a system of two coupled non-linear n×n matrix equations. This density is interpreted as the Brown measure of a linear combination of free circular elements with matrix coefficients on a non-commutative probability space. It is radially symmetric, real analytic in the radial variable and strictly positive on a disk around the origin in the complex plane with a discontinuous drop to zero at the edge. The radius of the disk is given explicitly in terms of the covariances of the entries of X. We show convergence down to local spectral scales just slightly above the typical eigenvalue spacing with an optimal rate of convergence.