In this paper, we consider the problem of robustly estimating a structured covariance matrix (CM). Specifically, we focus on CM structures that involve Kronecker products of low rank matrices, which often arise in the context of array processing (e.g. in MIMO-Radar, COLD array, and STAP). To tackle this problem, we derive a new Constrained Tyler's Estimators (CTE), which is defined as the minimizer of the cost function associated to Tyler's estimator under Kronecker structural constraint. Algorithms to compute these new CTEs are derived based on the Majorization-Minimization algorithmic framework.