We report five Local Volume dwarf galaxies (two of which are presented here for the first time) uncovered during a comprehensive archival search for optical counterparts to ultra-compact high velocity clouds (UCHVCs). The UCHVC population of HI clouds are thought to be candidate gas-rich, low mass halos at the edge of the Local Group and beyond, but no comprehensive search for stellar counterparts to these systems has been presented. Careful visual inspection of all publicly available optical and ultraviolet imaging at the position of the UCHVCs revealed six blue, diffuse counterparts with a morphology consistent with a faint dwarf galaxy beyond the Local Group. Optical spectroscopy of all six candidate dwarf counterparts show that five have an H$alpha$-derived velocity consistent with the coincident HI cloud, confirming their association, the sixth diffuse counterpart is likely a background object. The size and luminosity of the UCHVC dwarfs is consistent with other known Local Volume dwarf irregular galaxies. The gas fraction ($M_{HI}/M_{star}$) of the five dwarfs are generally consistent with that of dwarf irregular galaxies in the Local Volume, although ALFALFA-Dw1 (associated with ALFALFA UCHVC HVC274.68+74.70$-$123) has a very high $M_{HI}/M_{star}$$sim$40. Despite the heterogenous nature of our search, we demonstrate that the current dwarf companions to UCHVCs are at the edge of detectability due to their low surface brightness, and that deeper searches are likely to find more stellar systems. If more sensitive searches do not reveal further stellar counterparts to UCHVCs, then the dearth of such systems around the Local Group may be in conflict with $Lambda$CDM simulations.