We have performed a pilot study of mass loss predictions for late-type Wolf-Rayet (WR) stars as a function of metal abundance, over a range between 10(-5) <= (Z/Z(.)) <= 10. We find that the winds of nitrogen-rich Wolf-Rayet stars are dominated by iron lines, with a dependence of mass loss on Z similar to that of massive OB stars. For more evolved, carbon-rich, WR stars the wind strength is also found to be dependent on the Fe abundance, so that they depend on the chemical environment of the host galaxy, but with a mass loss metallicity dependence that is less steep than for OB stars. Our finding that WR mass loss is Z-dependent is a new one, with important consequences for black hole formation and X-ray population studies in external galaxies. A further finding of our study is that the Z dependence of C-rich WR stars becomes weaker at metallicities below Z/Z(.) less than or similar to 1/10, and mass loss no longer declines once the metal abundance drops below (Z/Z(.)) similar or equal to 10(-3). This is the result of an increased importance of radiative driving by intermediate mass elements, such as carbon. In combination with rapid rotation and/or proximity to the Eddington limit - likely to be relevant for massive Population III stars - this effect may indicate a role for mass loss in the appearance and evolution of these objects, as well as a potential role for stellar winds in enriching the intergalactic medium of the early Universe.