The nearby irregular galaxy Holmberg II has been extensively mapped in HI using the Very Large Array (VLA), revealing intricate structure in its interstellar gas component (Puche et al. 1992). An analysis of these structures shows the neutral gas to contain a number of expanding HI holes. The formation of the HI holes has been attributed to multiple supernova events occurring within wind-blown shells around young, massive star clusters, with as many as 10-200 supernovae required to produce many of the holes. From the sizes and expansion velocities of the holes, Puche et al. assigned ages of ~10^7 to 10^8 years. If the supernova scenario for the formation of the HI holes is correct, it implies the existence of star clusters with a substantial population of late-B, A and F main sequence stars at the centers of the holes. Many of these clusters should be detectable in deep ground-based CCD images of the galaxy. In order to test the supernova hypothesis for the formation of the HI holes, we have obtained and analyzed deep broad-band BVR and narrow-band H-alpha images of Ho II. We compare the optical and HI data and search for evidence of the expected star clusters in and around the HI holes. We also use the HI data to constrain models of the expected remnant stellar population. We show that in several of the holes the observed upper limits for the remnant cluster brightness are strongly inconsistent with the SNe hypothesis described in Puche et al. Moreover, many of the HI holes are located in regions of very low optical surface brightness which show no indication of recent star formation. Here we present our findings and explore possible alternative explanations for the existence of the HI holes in Ho II, including the suggestion that some of the holes were produced by Gamma-ray burst events.