This paper presents an on-line self-test architecture for hardware implementation of the Advanced Encryption Standard (AES). The solution exploits the inherent spatial replications of a parallel architecture for implementing functional redundancy at low cost. We show that the solution is very effective for on-line fault detection while keeping the area overhead very low. Moreover, the architectural modification for on-line test does not weaken the device with respect to side-channel attacks based on power analysis.