Genetic robustness, the invariance of the phenotype in the face of genetic perturbations, can endow the organism with reduced susceptibility to mutations. A large body of work in recent years has focused on the origins, mechanisms, and consequences of robustness in a wide range of biological systems. Despite the apparent prevalence of mutational robustness in nature, however, its evolutionary origins are still unclear. Does robustness evolve directly by natural selection or is it merely a correlated byproduct of other phenotypic traits? By examining microRNA (miRNA) genes of several eukaryotic species, we show that the structure of miRNA precursor stem-loops exhibits a significantly high level of mutational robustness in comparison with random RNA sequences with similar stem-loop structures. Hence, this excess robustness of miRNA goes beyond the intrinsic robustness of the stem-loop hairpin structure. Furthermore, we show that it is not the byproduct of a base composition bias or of thermodynamic stability. These findings suggest that the excess robustness of miRNA stem-loops is the result of direct evolutionary pressure toward increased robustness. We further demonstrate that this adaptive robustness evolves to compensate for structures with low intrinsic robustness.