The mechanical behavior of biocompatible ultrafine-grained (UFG) Niobium Zirconium alloy (NbZr), processed by Equal Channel Angular Processing (ECAP), was investigated under several loading conditions with a focus on fatigue properties and the effect of a simulated body fluid environment. Mechanical tests were accompanied by microstructural investigations in order to characterize the damage mechanisms prevalent. As compared to conventional grain size material, UFG NbZr exhibits high strength along with unaltered ductility. Fatigue properties were found to be improved in both the low-cycle (LCF) and the high-cycle fatigue (HCF) regime. This was attributed to the pronounced stability of the UFG microstructure, which is promoted by using efficient ECAP routes. The application of an internal oxidation heat treatment at low partial pressures of oxygen leads to significant surface hardening without surface disruption and therefore promotes further improved wear- and HCF properties. Due to its stable dense passive oxide layer UFG NbZr is characterized by a high corrosion resistance in simulated body fluid, which is in the range of titanium alloys. Under LCF and HCF conditions, no alteration of the fatigue properties due to corrosive attack was observed. Even under more critical fatigue crack propagation conditions, a slight acceleration of crack growth was observed only in the near-threshold regime upon a significant reduction of test frequency.