We present a catalog of 59 ultra-compact high velocity clouds (UCHVCs) extracted from the 40% complete ALFALFA HI-line survey. The ALFALFA UCHVCs have median flux densities of 1.34Jy.km/s, median angular diameters of 10', and median velocity widths of 23km/s. We show that the full UCHVC population cannot easily be associated with known populations of high velocity clouds. Of the 59 clouds presented here, only 11 are also present in the compact cloud catalog extracted from the commensal GALFA-HI survey, demonstrating the utility of this separate dataset and analysis. Based on their sky distribution and observed properties, we infer that the ALFALFA UCHVCs are consistent with the hypothesis that they may be very low mass galaxies within the Local Volume. In that case, most of their baryons would be in the form of gas, and because of their low stellar content, they remain unidentified by extant optical surveys. At distances of ~1Mpc, the UCHVCs have neutral hydrogen (HI) masses of ~10^5^-10^6^M_{sun}_, HI diameters of ~2-3kpc, and indicative dynamical masses within the HI extent of ~10^7^-10^8^M_{sun}_, similar to the Local Group ultra-faint dwarf Leo T. The recent ALFALFA discovery of the star-forming, metal-poor, low mass galaxy Leo P demonstrates that this hypothesis is true in at least one case. In the case of the individual UCHVCs presented here, confirmation of their extragalactic nature will require further work, such as the identification of an optical counterpart to constrain their distance.