When the feature size of photonic structures becomes comparable or even smaller than the wavelength of light, the fabrication imperfections inevitably introduce disorder that may eliminate many functionalities of subwavelength photonic devices. Here we suggest a novel concept to achieve a robust band gap which can endure disorder beyond 30% as a result of the transition from photonic crystals to Mie-resonant metamaterials. By utilizing Mie-resonant metamaterials with high refractive index, we demonstrate photonic waveguides and cavities with strong robustness to position disorder, thus providing a novel approach to the band-gap-based nanophotonic devices with new properties and functionalities.