Reinhard Gehlen nació en Erfurt, Alemania, en el seno de una librería. Fue criado como católico romano. Se alistó en el ejército en 1920 y se graduó en la Escuela de Estado Mayor alemana en 1935. Con el rango de capitán, fue adscrito al Estado Mayor del Ejército a finales de 1935.
En 1939, fue ascendido al rango de mayor. En 1939, fue oficial de Estado Mayor de una división de infantería durante la invasión de Polonia. En 1940, se convirtió en el oficial de enlace del Comandante en Jefe del Ejército, el Mariscal de Campo Walther von Brauchitsch, y más tarde ese mismo año fue transferido al personal del Jefe del Estado Mayor, el General Franz Halder.
En julio de 1941, fue ascendido al rango de teniente coronel, y poco después se convirtió en oficial superior de inteligencia en el frente ruso. En 1942, el coronel Henning von Tresckow, el coronel Claus von Stauffenberg y el general Adolf Heusinger se pusieron en contacto con él para que participara en el asesinato de Hitler; cuando el complot de julio fracasó, Gehlen pudo encubrir su implicación (su participación no fue significativa) durante las investigaciones posteriores.
En diciembre de 1944, fue ascendido al rango de general de división y se le encargó la recopilación de información. En marzo de 1945, Gehlen y algunos de sus oficiales superiores microfilmaron las existencias de su organización Fremde Heere Ost y enterraron las películas en bidones herméticos en varios lugares de los Alpes austriacos. El 22 de mayo de 1945, se entregó al Cuerpo de Contrainteligencia del ejército estadounidense en Baviera, en el sur de Alemania.
Después de la guerra, Gehlen ofreció sus archivos de inteligencia, su conocimiento de las organizaciones militares rusas y sus contactos en la Unión Soviética a los estadounidenses a cambio de la libertad de varios oficiales alemanes, incluido él mismo.
La oferta fue aceptada y el nombre de Gehlen, junto con el de sus antiguos oficiales superiores, desapareció de las listas de prisioneros de guerra. Poco después, Gehlen y otras siete personas recogieron los tambores enterrados en secreto. El 20 de septiembre de 1945, Gehlen y tres de sus oficiales fueron trasladados a Estados Unidos para empezar a trabajar en la Oficina de Servicios Estratégicos.
Entre sus primeras contribuciones a la OSS se encuentra la revelación de varios oficiales de la OSS que eran, en secreto, miembros del Partido Comunista estadounidense.
En julio de 1946, Gehlen fue liberado oficialmente del cautiverio estadounidense y regresó a Alemania. Desde Alemania, creó una organización formada por 350 antiguos oficiales de inteligencia alemanes y operó bajo la cobertura de la Organización de Desarrollo Industrial del Sur de Alemania en Pullach, Alemania, cerca de Munich. Esta organización llegaría a tener 4.000 agentes encubiertos.
Sus agentes, con el nombre en clave de “Hombres V” y su grupo apodado “Organización Gehlen”, fueron instrumentos de la Agencia Central de Inteligencia de EEUU en Alemania contra las naciones soviéticas durante la Guerra Fría.
La Organización Gehlen fue evaluada posteriormente como ineficaz a la hora de recopilar información valiosa de las naciones soviéticas, aunque misiones exitosas como la Operación Crucigrama (infiltración de 5.000 anticomunistas en Europa del Este y Rusia) y el descubrimiento de la unidad de asesinatos soviética conocida como SMERSH demostraron la valía de la organización.
En 1955, la Organización Gehlen pasó a manos de la República Federal de Alemania bajo el gobierno de Konrad Adenauer. El 1 de abril de 1956, la organización constituyó la base del recién creado Servicio Federal de Inteligencia, con Gehlen al frente con el título de presidente. En 1968, se retiró a causa de un escándalo político entre los altos cargos del Servicio Federal de Inteligencia.