We report the discovery, tracking and detection circumstances for 85 trans-Neptunian objects (TNOs) from the first 42 deg$^{2}$ of the Outer Solar System Origins Survey (OSSOS). This ongoing $r$-band Solar System survey uses the 0.9 deg$^{2}$ field-of-view MegaPrime camera on the 3.6 m Canada-France-Hawaii Telescope. Our orbital elements for these TNOs are precise to a fractional semi-major axis uncertainty $<0.1\%$. We achieve this precision in just two oppositions, as compared to the normal 3-5 oppositions, via a dense observing cadence and innovative astrometric technique. These discoveries are free of ephemeris bias, a first for large trans-Neptunian surveys. We also provide the necessary information to enable models of TNO orbital distributions to be tested against our TNO sample. We confirm the existence of a cold "kernel" of objects within the main cold classical Kuiper belt, and infer the existence of an extension of the "stirred" cold classical Kuiper belt to at least several AU beyond the 2:1 mean motion resonance with Neptune. We find that the population model of Petit et al. (2011) remains a plausible representation of the Kuiper belt. The full survey, to be completed in 2017, will provide an exquisitely characterized sample of important resonant TNO populations, ideal for testing models of giant planet migration during the early history of the Solar System.