Seu nome é uma referência ao matemático estado-unidense
Stephen Cole Kleene, que, entretanto, não foi o responsável por sua definição. Ele introduziu as
expressões regulares e questionou um conjunto completo de
axiomas que permitiriam a derivação de todas as equações entre expressões regulares. O problema foi estudado originalmente por
John Horton Conway com o nome de álgebras regulares. os axiomas das álgebras de Kleene resolvem o problema, como demonstrado por Dexter Kozen.