The quantum spin Hall (QSH) phase is a time reversal invariant electronic state with a bulk electronic band gap that supports the transport of charge and spin in gapless edge states. We show that this phase is associated with a novel Z2 topological invariant, which distinguishes it from an ordinary insulator. The Z2 classification, which is defined for time reversal invariant Hamiltonians, is analogous to the Chern number classification of the quantum Hall effect. We establish the Z2 order of the QSH phase in the two band model of graphene and propose a generalization of the formalism applicable to multiband and interacting systems.