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.

Tras la guerra, Kleinheisterkamp se unió al grupo paramilitar de los Freikorps y después sirvió en el Reichswehr.

Su carrera se estancó en junio de 1938 cuando experimentó problemas graves legales y disciplinarios.

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.

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.