Swimming microrobots have the potential to be used in medical applications such as targeted drug delivery. The challenges for navigating microrobots in the human body lie not only in the viscosity of body fluids but also in the existence of different types of fibers and cells such as blood cells or protein strands. This paper investigates artificial bacterial flagella (ABFs), which are helical microrobots actuated by an external magnetic field, in methyl cellulose solutions of different concentrations. It can be shown that the microrobots can be propelled in these gel-like heterogeneous solutions and successful swimming was demonstrated in solutions with a viscosity of more than 20 times that of water. Furthermore, results indicate that the existence of fibers can help ABFs swim more effectively, which agrees with previous experimental results reported for natural bacteria.