The Arecibo L-Band Feed Array Zone of Avoidance (ALFA ZOA) Deep Survey is the deepest and most sensitive blind Hi survey undertaken in the ZOA. ALFA ZOA Deep will cover about 300 square degrees of sky behind the Galactic plane in both the inner (30 deg < l < 75 deg; b < |2 deg|) and outer (175 deg < l < 207 deg; -2 deg < b < +1 deg) Galaxy, using the Arecibo Radio Telescope. First results from the survey have found 61 galaxies within a 15 square degree area centered on l = 192 deg and b = -2 deg. The survey reached its expected sensitivity of rms = 1 mJy at 9 km/s channel resolution, and is shown to be complete above integrated flux, F_HI = 0.5 Jy km/s. The positional accuracy of the survey is 28 arcsec and detections are found out to a recessional velocity of nearly 19,000 km/s. The survey confirms the extent of the Orion and Abell 539 clusters behind the plane of the Milky Way and discovers expansive voids, at 10,000 km/s and 18,000 km/s. 26 detections (43%) have a counterpart in the literature, but only two of these have known redshift. Counterparts are 20% less common beyond v_hel = 10,000 km/s and 33% less common at extinctions higher than AB = 3.5 mag. ALFA ZOA Deep survey is able to probe large scale structure beyond redshifts that even the most modern wide-angle surveys have been able to detect in the Zone of Avoidance at any wavelength.