We construct generalizations of the Kerr black holes by including higher-curvature corrections in the form of the Gauss-Bonnet density coupled to the dilaton. We show that the domain of existence of these Einstein-Gauss-Bonnet-dilaton (EGBD) black holes is bounded by the Kerr black holes, the critical EGBD black holes, and the singular extremal EGBD solutions. The angular momentum of the EGBD black holes can exceed the Kerr bound. The EGBD black holes satisfy a generalized Smarr relation. We also compare their innermost stable circular orbits with those of the Kerr black holes and show the existence of differences which might be observable in astrophysical systems.