We report the results of a search for molecular oxygen (O2) toward the Orion Bar, a prominent photodissociation region at the southern edge of the HII region created by the luminous Trapezium stars. We observed the spectral region around the frequency of the O2 N_J = 3_3 - 1_2 transition at 487 GHz and the 5_4 - 3_4 transition at 774 GHz using the Heterodyne Instrument for the Far Infrared on the Herschel Space Observatory. Neither line was detected, but the 3sigma upper limits established here translate to a total line-of-sight O2 column density < 1.5 10^16 cm^-2 for an emitting region whose temperature is between 30K and 250 K, or < 1 10^16 cm^-2 if the O2 emitting region is primarily at a temperature of ~< 100 K. Because the Orion Bar is oriented nearly edge-on relative to our line of sight, the observed column density is enhanced by a factor estimated to be between 4 and 20 relative to the face-on value. Our upper limits imply that the face-on O2 column density is less than 4 10^15 cm^-2, a value that is below, and possibly well below, model predictions for gas with a density of 10^4 - 10^5 cm^-3 exposed to a far ultraviolet flux 10^4 times the local value, conditions inferred from previous observations of the Orion Bar. The discrepancy might be resolved if: (1) the adsorption energy of O atoms to ice is greater than 800 K; (2) the total face-on Av of the Bar is less than required for O2 to reach peak abundance; (3) the O2 emission arises within dense clumps with a small beam filling factor; or, (4) the face-on depth into the Bar where O2 reaches its peak abundance, which is density dependent, corresponds to a sky position different from that sampled by our Herschel beams.