We synthesize knowledge from numerical weather prediction, inverse theory and statistics to address the problem of estimating a high-dimensional covariance matrix from a small number of samples. This problem is fundamental in statistics, machine learning/artificial intelligence, and in modern Earth science. We create several new adaptive methods for high-dimensional covariance estimation, but one method, which we call NICE (Noise-Informed Covariance Estimation), stands out because it has three important properties: (i) NICE is conceptually simple and computationally efficient; (ii) NICE guarantees symmetric positive semi-definite covariance estimates; and (iii) NICE is largely tuning-free. We illustrate the use of NICE on a large set of Earth-science-inspired numerical examples, including cycling data assimilation, geophysical inversion of field data, and training of feed-forward neural networks with time-averaged data from a chaotic dynamical system. Our theory, heuristics and numerical tests suggest that NICE may indeed be a viable option for high-dimensional covariance estimation in many Earth science problems.