In this paper we propose an on-line self-test architecture for hardware implementations of Advanced Encryption Standard (AES). The solution assumes a parallel architecture and exploits the inherent spatial replications of this implementation. Because Substitution boxes (S-Box) represent the largest hardware in this architecture, we focus on faults affecting these S-Boxes and propose a trade-off between hardware overhead and fault latency. We show that our solution is very effective while keeping the area overhead very low. Moreover, this architecture does not weak the device with respect to side-channel attacks based on power analysis. On the contrary, it makes more difficult this type of attack.