Kleene algebras with tests provide a natural framework for equational specification and verification. Kleene algebras with tests and related systems have been used successfully in basic safety analysis, source-to-source program transformation, and concurrency control. The equational theory of Kleene algebras with tests has been shown to be decidable in at most exponential time by an efficient reduction to Propositional Dynamic Logic. In this paper we prove that the theory is PSPACE-complete.