Rotary bending fatigue tests were conducted on a number of different grades of austempered ductile irons (ADIs). These ADIs were produced from four different base-irons with various nodularity, nodule counts, and alloy elements. Each base-iron was austenitized at 900°C and then austempered at 300 and ∼360°C, respectively, to generate different ADI matrix structures. No simple rule between high-cycle fatigue (HCF) strength and monotonic tensile strength and hardness in ADI was observed, as the HCF strength depended mainly on the toughness and amount of retained austenite. The effects of austempering temperatures, nodularity, nodule count, and retained austenite content on the HCF behavior are discussed. Fractography with scanning electron microscopy (SEM) was conducted to determine the HCF fracture origins and failure mechanisms.