The Arecibo L-band Feed Array (ALFA) is being used to conduct a low-Galactic latitude survey, to map the distribution of galaxies and large-scale structures behind the Milky Way through detection of galaxies' neutral hydrogen (HI) 21-cm emission. This Zone of Avoidance (ZOA) survey finds new HI galaxies which lie hidden behind the Milky Way, and also provides redshifts for partially-obscured galaxies known at other wavelengths. Before the commencement of the full survey, two low-latitude precursor regions were observed, totalling 138 square degrees, with 72 HI galaxies detected. Detections through the inner Galaxy generally have no cataloged counterparts in any other waveband, due to the heavy extinction and stellar confusion. Detections through the outer Galaxy are more likely to have 2MASS counterparts. We present the results of these precursor observations, including a catalog of the detected galaxies, with their HI parameters. The survey sensitivity is well described by a flux- and linewidth-dependent signal-to-noise ratio of 6.5. ALFA ZOA galaxies which also have HI measurements in the literature show good agreement between our measurements and previous work. The inner Galaxy precursor region was chosen to overlap the HI Parkes Zone of Avoidance Survey so ALFA performance could be quickly assessed. The outer Galaxy precursor region lies north of the Parkes sky. Low-latitude large-scale structure in this region is revealed, including an overdensity of galaxies near l = 183 deg and between 5000 - 6000 km/s in the ZOA. The full ALFA ZOA survey will be conducted in two phases: a shallow survey using the observing techniques of the precursor observations, and also a deep phase with much longer integration time, with thousands of galaxies predicted for the final catalog.