The problem of estimating complex covariance matrices is considered. The objective is to obtain a well behaving estimator that circumvents the weaknesses of the standard sample covariance and regularized estimators. To this end, we use a variational technique that previously has been successfully applied in the real data case. As a side result, an important identity for complex Wishart distributions is also derived. Simulations indicate substantial improvements compared to both the sample covariance and the regularized estimator.