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 for on-line fault detection while keeping the area overhead very low. Moreover, it does not weak the device with respect to side-channel attacks based on power analysis.