Fault injection based attacks on cryptographic devices aim at recovering the secret keys by inducing an error in the computation process. They are now considered a real threat and countermeasures against them must be taken. In this paper, we describe an extension to an existing AES architecture proposed by Mangard et al. [13], which provides error detection and fault tolerance by exploiting the high regularity of the architecture. The proposed design is capable of performing online error detection and reconfiguring internal data paths to protect against faults occurring in the computation process. We also describe how different redundancy levels provide protection against different numbers of errors. The presented design incorporating fault detection and tolerance has the same throughput as the base architecture but incurs a non-negligible area overhead. This overhead is about 40% for the fault detection circuitry and 134% for the entire fault detection and tolerance (through reconfiguration). Although quite high, this overhead is still lower than for reference solutions such as duplication (providing detection) and triple modular redundancy (providing fault masking).