It has long been known that some microswimmers seem to swim counter-intuitively faster when the viscosity of the surrounding fluid is increased, whereas others slow down. This conflicting dependence of the swimming velocity on the viscosity is poorly understood theoretically. Here we explain that any mechanical microswimmer with an elastic degree of freedom in a simple Newtonian fluid can exhibit both kinds of response to an increase in the fluid viscosity for different viscosity ranges, if the driving is weak. The velocity response is controlled by a single parameter Γ, the ratio of the relaxation time of the elastic component of the swimmer in the viscous fluid and the swimming stroke period. This defines two velocity–viscosity regimes, which we characterize using the bead-spring microswimmer model and analyzing the different forces acting on the parts of this swimmer. The analytical calculations are supported by lattice-Boltzmann simulations, which accurately reproduce the two velocity regimes for the predicted values of Γ.