Introdujo la operación clausura de Kleene, denotada por el símbolo V*.
Recibió su título de artes en el Amherts College en 1930.
Desde 1930 a 1935 fue un estudiante graduado y asistente investigador en la Universidad de Princeton, donde recibió su doctorado en Matemáticas en 1934, supervisado por Alonzo Church, por una tesis titulada Una teoría de Enteros Positivos en Lógica Formal.
Desde 1939 a 1940 fue un visitante escolar en Princeton del Institute for Advanced Study (Instituto para Estudio Avanzado), donde fundó la teoría de las funciones recursivas, un área de interés que sería investigada por él durante toda su vida.
Ávido escalador de montañas, Kleene tuvo fuerte interés en la naturaleza y el ambiente, y participó en muchas causas a favor de conservación del medioambiente.