The cosmic optical background is an important observable that constrains energy production in stars and more exotic physical processes in the universe, and provides a crucial cosmological benchmark against which to judge theories of structure formation. Measurement of the absolute brightness of this background is complicated by local foregrounds like the Earths atmosphere and sunlight reflected from local interplanetary dust, and large discrepancies in the inferred brightness of the optical background have resulted. Observations from probes far from the Earth are not affected by these bright foregrounds. Here we analyze data from the Long Range Reconnaissance Imager (LORRI) instrument on NASAs New Horizons mission acquired during cruise phase outside the orbit of Jupiter, and find a statistical upper limit on the optical backgrounds brightness similar to the integrated light from galaxies. We conclude that a carefully performed survey with LORRI could yield uncertainties comparable to those from galaxy counting measurements.