We study the capabilities of IceCube to search for sterile neutrinos with masses above 10 eV by analyzing its $\nu_\mu$ disappearance atmospheric neutrino sample. We find that IceCube is not only sensitive to the mixing of sterile neutrinos to muon neutrinos, but also to the more elusive mixingwith tau neutrinos through matter effects. The currently released 1-year data shows a mild (around 2$\sigma$) preference for non-zero sterile mixing, which overlaps with the favoured region for the sterileneutrino interpretation of the ANITA upward shower. Although the null results from CHORUS and NOMAD on $\nu_mu$ to $\nu_\tau$ oscillations in vacuum disfavour the hint from the IceCube 1-year data, therelevant oscillation channel and underlying physics are different. At the 99% C.L. an upper boundis obtained instead that improves over the present Super-Kamiokande and DeepCore constraintsin some parts of the parameter space. We also investigate the physics reach of the roughly 8 yearsof data that is already on tape as well as a forecast of 20 years data to probe the present hint orimprove upon current constraints.