Klebs nació en Braunsberg (Braniewo), Prusia. Estudió en la Universidad Humboldt de Berlín con Theodor Mommsen y Heinrich von Treitschke, recibiendo su doctorado en 1876 y su habilitación en 1883.^[1]​ Posteriormente, se desempeñó como profesor asociado en Berlín. Junto con Hermann Dessau y Paul von Rohden, participó en la producción de la primera edición de la Prosopographia Imperii Romani de la Academia de Ciencias de Prusia.^[2]​ Klebs preparó el primer volumen, las letras AC, que apareció en 1897.^[3]​

A partir de 1906, fue profesor de historia antigua en la Universidad de Marburg. A causa de una enfermedad grave, fue puesto en licencia en 1913 y relevado de sus deberes académicos al año siguiente. Murió en Marburgo.^[1]​

Klebs se centró en la historia de la antigua Roma, como la Historia Augusta, la Historia Apollonii y también los estudios sobre el cortesano Petronio. Además, hizo importantes contribuciones a la Realencyclopädie der classischen Altertumswissenschaft. Los siguientes son algunos de sus principales esfuerzos literarios:^[4]​

• Prosopographia Imperii Romani saec. I. II. III. Band 1 A – C, Reimer, Berlín, 1897.
• Die Erzählung von Apollonius aus Tyrus. Eine geschichtliche Untersuchung über ihre lateinische Urform und ihre späteren Bearbeitungen. Berlín, 1899.
• Die Sammlung der Scriptores historiae Augustae, Rheinisches Museum für Philologie Band 45, 1890.^[3]​
• Petroniana. Anhang I. Die municipalen Praetoren. Anhang II. Vrbs, oppidvm, civitas, patria.
• De scriptoribus aetatis Sullanae. Berlin 1876, (Berlín, Universität, Dissertation, 1876).
• Zur Composition von Petronius Satirae. En: Philologus. Band 47, 1889, S. 623–635, doi 10.1524/phil.1888.47.14.623
• Das dynastische Element in der Geschichtsschreibung der römischen Kaiserzeit. In: Historische Zeitschrift. Band 61 = NF 25, Heft 2, 1889, S. 213–245, JSTOR 27596666