The properties of the first-discovered interstellar object (ISO), 1I/2017 (`Oumuamua), differ from both Solar System asteroids and comets, casting doubt on a protoplanetary disk origin. In this study, we investigate the possibility that it formed with a substantial H2 ice component in the starless core of a giant molecular cloud. While interstellar solid hydrogen has yet to be detected, this constituent would explain a number of the ISOs properties. We consider the relevant processes required to build decameter-sized, solid hydrogen bodies and assess the plausibility of growth in various size regimes. Via an energy balance argument, we find that the most severe barrier to formation is the extremely low temperature required for the favorability of molecular hydrogen ice. However, if deposition occurs, we find that the turbulence within starless cores is conducive for growth into kilometer-sized bodies on sufficiently short timescales. Then, we analyze mass loss in the interstellar medium and determine the necessary size for a hydrogen object to survive a journey to the Solar System as a function of ISO age. Finally, we discuss the implications if the H2 explanation is correct, and we assess the future prospects of ISO science. If hydrogen ice ISOs do exist, our hypothesized formation pathway would require a small population of porous, 100 micron dust in a starless core region that has cooled to 2.8K via adiabatic expansion of the surrounding gas and excellent shielding from electromagnetic radiation and cosmic rays.