In this paper, we consider the robust covariance estimation problem in the non-Gaussian set-up. In particular, Tyler's M-estimator is adopted for samples drawn from a heavy-tailed elliptical distribution. For some applications, the covariance matrix naturally possesses certain structure. Therefore, incorporating the prior structure information in the estimation procedure is beneficial to improving estimation accuracy. The problem is formulated as a constrained minimization of the Tyler's cost function, where the structure is characterized by the constraint set. A numerical algorithm based on majorization-minimization is derived for general structures that can be characterized as a convex set, where a sequence of convex programming is solved. For the set of matrices that can be decomposed as the sum of rank one positive semidefinite matrices, which has a wide range of applications, the algorithm is modified with much lower complexity. Simulation results demonstrate that the proposed structure-constrained Tyler's estimator achieves smaller estimation error than the unconstrained case.