Using the Very Large Array and ALMA, we have obtained CO(2–1), [C II], and [N II] line emission and multiple dust continuum measurements in a sample of "normal" galaxies at z = 5–6. We report the highest-redshift detection of low-J CO emission from a Lyman break galaxy, at z ~ 5.7. The CO line luminosity implies a massive molecular gas reservoir of (1.3 ± 0.3)(α CO/4.5 M_⊙ (K km s^(−1) pc^2)^(−1)) × 10^(11) M_⊙, suggesting low star formation efficiency with a gas depletion timescale of order ~1 Gyr. This efficiency is much lower than traditionally observed in z ≳ 5 starbursts, indicating that star-forming conditions in main-sequence galaxies at z ~ 6 may be comparable to those of normal galaxies probed up to z ~ 3 to date but with rising ga...