We report evidence of cyclotron resonance features from the Soft Gamma Repeater SGR 1806-20 in outburst, detected with the Rossi X-ray Timing Explorer in the spectrum of a long, complex precursor that preceded a strong burst. The features consist of a narrow 5.0 keV absorption line with modulation near its second and third harmonics (at 11.2 keV and 17.5 keV respectively). The line features are transient and are detected in the harder part of the precursor. The 5.0 keV feature is strong, with an equivalent width of ~ 500 eV and a narrow width of less than 0.4 keV. Interpreting the features as electron cyclotron lines in the context of accretion models leads to a large mass-radius ratio (M/R > 0.3 M_sun/km) that is inconsistent with neutron stars or that requires a low (5-7)x10^{11} G magnetic field that is unlikely for SGRs. The line widths are also narrow compared with those of electron cyclotron resonances observed so far in X-ray pulsars. In the magnetar picture, the features are plausibly explained as ion cyclotron resonances in an ultra-strong magnetic field that have recently been predicted from magnetar candidates. In this view, the 5.0 keV feature is consistent with a proton cyclotron fundamental whose energy and width are close to model predictions. The line energy would correspond to a surface magnetic field of 1.0x10^{15} G for SGR 1806-20, in good agreement with that inferred from the spin-down measure in the source.