Assuming our Solar System as typical, exomoons may outnumber exoplanets. If their habitability fraction is similar, they would thus constitute the largest portion of habitable real estate in the Universe. Icy moons in our Solar System, such as Europa and Enceladus, have already been shown to possess liquid water, a prerequisite for life on Earth. We intend to investigate under what circumstances small, icy moons may sustain subsurface oceans and thus be subsurface habitable. We pay specific attention to tidal heating. We made use of a phenomenological approach to tidal heating. We computed the orbit averaged flux from both stellar and planetary (both thermal and reflected stellar) illumination. We then calculated subsurface temperatures depending on illumination and thermal conduction to the surface through the ice shell and an insulating layer of regolith. We adopted a conduction only model, ignoring volcanism and ice shell convection as an outlet for internal heat. In doing so, we determined at which depth, if any, ice melts and a subsurface ocean forms. We find an analytical expression between the moons physical and orbital characteristics and the melting depth. Since this expression directly relates icy moon observables to the melting depth, it allows us to swiftly put an upper limit on the melting depth for any given moon. We reproduce the existence of Enceladus subsurface ocean; we also find that the two largest moons of Uranus (Titania & Oberon) could well sustain them. Our model predicts that Rhea does not have liquid water. Habitable exomoon environments may be found across an exoplanetary system, largely irrespective of the distance to the host star. Small, icy subsurface habitable moons may exist anywhere beyond the snow line. This may, in future observations, expand the search area for extraterrestrial habitable environments beyond the circumstellar habitable zone.