Double-negative refractive index materials have attracted sustained experimental and theoretical interest because they can display a range of surprising optical phenomena, including negative Doppler shifts and perfect lensing. Double-negative indexes have been achieved experimentally in engineered metamaterials; however, these materials become increasingly challenging to fabricate at shorter wavelengths, and at optical wavelengths only 2D negative index materials have been achieved. Here, it is shown that a double-negative index can occur in a natural material, near narrow optical transitions of dielectric crystals stoichiometric in a rare-earth ion. Optical measurements of two candidate materials, the magnetically-ordered erbium crystals, ErCl3 center dot 6H(2)O and (LiErF4)-Li-7, which have ultra-narrow optical linewidths of 3 GHz and 250 MHz, respectively, in the telecom band are presented. It is shown that the spectral density of (LiErF4)-Li-7 is sufficient to achieve a negative index at 1530 nm. This material can enable the exploration of negative refractive index effects at optical wavelengths in a truly 3D, natural medium.