We present a spectroscopic analysis of VLT/X-Shooter observations of six O-type stars in the low-metallicity (Z ~ 1/7 Z\odot) galaxies IC 1613, WLM and NGC 3109. The stellar and wind parameters of these sources allow us, for the first time, to probe the mass-loss versus metallicity dependence of stellar winds below that of the Small Magellanic Cloud (at Z ~ 1/5Z\odot) by means of a modified wind momentum versus luminosity diagram. The wind strengths that we obtain for the objects in WLM and NGC 3109 are unexpectedly high and do not agree with theoretical predictions. The objects in IC 1613 tend towards a higher than expected mass-loss rate, but remain consistent with predictions within their error bars. We discuss potential systematic uncertainties in the mass-loss determinations to explain our results. However, if further scrutinization of these findings point towards an intrinsic cause for this unexpected sub-SMC mass-loss behavior, implications would include a higher than anticipated number of Wolf-Rayet stars and Ib/Ic supernovae in low-metallicity environments, but a reduced number of long-duration gamma-ray bursts produced through a single-star evolutionary channel.

9 pages, 3 figures; accepted for publication in The Astrophysical Journal Letters