On 2008 March 19, one of the brightest gamma-ray bursts (GRBs) ever recorded was detected by several groundand space-based instruments spanning the electromagnetic spectrum from radio to gamma rays. With a peak visual magnitude of 5.3, GRB 080319B was dubbed the “naked-eye” GRB, as an observer under dark skies could have seen the burst without the aid of an instrument. Presented here are results from observations of the prompt phase of GRB 080319B taken with the Milagro TeV observatory. The burst was observed at an elevation angle of 47 ◦ . Analysis of the data is performed using both the standard air shower method and the scaler or single-particle technique, which results in a sensitive energy range that extends from ∼ 5G eV to>20 TeV. These observations provide the only direct constraints on the properties of the high-energy gamma-ray emission from GRB 080319B at these energies. No evidence for emission is found in the Milagro data, and upper limits on the gamma-ray flux above 10 GeV are derived. The limits on emission between ∼25 and 200 GeV are incompatible with the synchrotron self-Compton model of gamma-ray production and disfavor a corresponding range (2 eV–16 eV) of assumed synchrotron peak energies. This indicates that the optical photons and soft (∼650 keV) gamma rays may not be produced by the same electron population.