Kleene algebras, whose investigation was initiated by Kleene and carried on by Conway, Salomaa, Kozen, and many others, are algebraic structures intended to capture the structure of events with iteration. They are additively-idempotent semirings with a unary operator, the Kleene asterate or *, which serves as a fixed point operator for repeated multiplication. Regular languages provide the prototypical example of Kleene algebras, while relational models with the asterate interpreted by reflexive transitive closure, tropical algebras, and various forms of process algebra arising in the context of programming language semantics provide additional examples indicating the ubiquity of this concept. Kozen showed how to define an asterate operation on square matrices over a Kleene algebra, thus adding matrix Kleene algebras to the repertoire of examples. Square matrices over a Kleene algebra have a natural interpretation as finite-state automata. We introduce Morita equivalence to the study of Kleene algebras, which is an equivalence relation extending isomorphism and obtained as the isomorphism relation of the category of Kleene algebras extended with all Kleene bimodules as morphisms and tensor product as composition. It turns out that Kleene algebras are Morita-rigid over the category of semirings, in the sense that if there are semiring bimodules between two Kleene algebras which witness that the semiring reducts of these Kleene algebras are Morita-equivalent, then this Morita equivalence is in fact witnessed by Kleene bimodules. This means that well-known characterizations of Morita equivalence from ring theory (which carry over to semiring theory) are applicable, and an immediate corollary is that Morita-equivalent Kleene algebras have equivalent categories of automata.