We consider the problem of robustifying high-dimensional structured estimation. Robust techniques are key in real-world applications, as these often involve outliers and data corruption. We focus on trimmed versions of structurally regularized M-estimators in the high-dimensional setting, including the popular Least Trimmed Squared estimator, as well as analogous estimators for generalized linear models, graphical models, using possibly non-convex loss functions. We present a general analysis of their statistical convergence rates and consistency, and show how to extend any algorithms for M-estimators to fit trimmed variants. We then take a closer look at the $\ell_1$-regularized Least Trimmed Squared estimator as a special case. Our results show that this estimator can tolerate a larger fraction of corrupted observations than state-of-the-art alternatives. The competitive performance of high-dimensional trimmed estimators is illustrated numerically using both simulated and real-world genomics data.