We have used existing data from the LORRI camera on board the New Horizons spacecraft to measure the brightness of the astronomical sky over the visible-light spectrum (0.4 < λ < 0.9 μm) within seven fields at high galactic latitude. The sky levels were measured while New Horizons was 42 to 45 AU from the Sun and have an average surface brightness of 26.0 V mag arcsec−2, or at least 10× fainter than the darkest sky available to the Hubble Space Telescope, highlighting the utility of New Horizons’ vantage point for detecting the cosmic optical background (COB). The fields sample a wide range of ecliptic latitudes, but their total sky levels are highly uniform, having a mean level of 33.2 ± 0.5 nW m−2 sr−1. Isolating the COB contribution to this total requires subtracting scattered light from bright stars and galaxies both inside and outside the fields, faint stars below the photometric detection-limit within the fields, and diffuse Milky Way light scattered by infrared cirrus, from the observed total sky measures. We derive a correction to remove newly identified residual zodiacal light from the IRIS 100μm all sky maps to generate two different estimates for the diffuse galactic light (DGL). Using these two DGL estimates yields a highly significant detection of the COB in the range 15.9 ± 4.2 (1.8 stat., 3.7 sys.) nW m−2 sr−1 to 18.7 ± 3.8 (1.8 stat., 3.3 sys.) nW m−2 sr−1 at the LORRI pivot wavelength of 0.608 μm. Subtraction of the integrated light of galaxies (IGL) fainter than the photometric detection-limit from the total COB level leaves a diffuse flux component of unknown origin in the range 8.8 ± 4.9 (1.8 stat., 4.5 sys.) nW m−2 sr−1 to 11.9 ± 4.6 (1.8 stat., 4.2 sys.) nW m−2 sr−1.