Nacido en 1893, Matthias Kleinheisterkamp se alistó en el Ejército prusiano en 1914 y sirvió tanto en el frente occidental como en el oriental durante la I Guerra Mundial. Durante su servicio en la guerra, se le concedieron ambas clases de la Cruz de Hierro y la Medalla de herido en plata. Tras la guerra, Kleinheisterkamp se unió al grupo paramilitar de los Freikorps y después sirvió en el Reichswehr. Se unió al Allgemeine-SS en noviembre de 1933, con el número de carné 132.399. Fue transferido al SS-Verfügungstruppe el 1 de abril de 1935 y fue asignado a la escuela de entrenamiento de las SS como instructor de infantería. En 1934, se unió a la Inspección de las SS-VT como oficial sénior, sirviendo a las órdenes de Paul Hausser.

El 20 de abril de 1937, Kleinheisterkamp ingresó en el NSDAP, con número de carné 4.158.838. Su carrera se estancó en junio de 1938 cuando experimentó problemas graves legales y disciplinarios. Fue reprendido por la Oficina Central de la Corte de las SS y licenciado hasta agosto de 1938. A su retorno al servicio activo fue asignado a la SS-Standarte Deutschland, que después se convertiría en las División SS Das Reich.

Con esta unidad, Kleinheisterkamp tomó parte en la invasión de Polonia, donde comandó el Grupo Kleinheisterkamp responsable en parte de la evacuación de ciudadanos y personal diplomático alemanes de Varsovia. En mayo de 1940, fue puesto al cargo de un regimiento de infantería dentro de la División SS Totenkopf bajo el mando global de Theodor Eicke. Después de que Eicke fuera herido en julio de 1941, Kleinheisterkamp fue, por poco tiempo, comandante de la Totenkopf, antes de ser remplazado por Georg Keppler. Después fue transferido primero a las SS-Führungshauptamt (Oficina Central de Dirección de las SS) y después a la División SS Das Reich.

Por su liderazgo de la Das Reich durante las operaciones en el frente oriental, Kleinheisterkamp recibió la Cruz de Caballero de la Cruz de Hierro. En junio de 1942, asumió el mando de la División SS Nord, liderando esta unidad hasta diciembre de 1943, cuando fue transferido a la reserva de las Waffen-SS. En enero de 1944, fue asignado al mando del VII Cuerpo SS Panzer, III Cuerpo SS Panzer, IV Cuerpo SS Panzer y al XI Cuerpo SS del Ejército.

Kleinheisterkamp fue hecho prisionero por las fuerzas soviéticas el 28 de abril de 1945 cerca de la población de Halbe, al sureste de Berlín. Se suicidó un día después en cautividad. Otras fuentes afirman que murió el 2 de mayo en la batalla de Halbe.^[1]​ Póstumamente, a Kleinheisterkamp se le concedieron las Hojas de Roble por su Cruz de Caballero.^[2]​

• SS-Hauptsturmführer: de abril de 1935
• SS-Sturmbannführer: 1 de junio de 1935
• SS-Obersturmbannführer: 20 de abril de 1937
• SS-Standartenführer: 18 de mayo de 1940
• SS-Oberführer: 19 de julio de 1940
• SS-Brigadeführer und Generalmajor der Waffen-SS: 9 de noviembre de 1941
• SS-Gruppenführer und Generaleutnant der Waffen-SS: 1 de mayo de 1943
• SS-Obergruppenführer und General der Waffen-SS: 1 de agosto de 1944

• Broche de la Cruz de Hierro (1939)
  • 2ª Clase (13 de septiembre de 1939)^[3]​
  • 1ª Clase (2 de octubre de 1939)^[3]​
• Cruz de Caballero de la Cruz de Hierro el 31 de marzo de 1942 como SS-Brigadeführer, Generalmajor de las Waffen-SS y comandante de la División-SS "Das Reich"^[4]​
• 871ª Hojas de Roble el 9 de mayo de 1945 (póstumamente) como SS-Obergruppenführer, Generalleutnant de las Waffen-SS y comandante general del XI. SS-Panzerkorps^[5]​
• Orden de la Cruz de la Libertad 1ª Clase con espadas^[6]​