Abstract: Deep-submicron technology allows billions of transistors on a single die, potentially running at gigahertz frequencies. According to the Semiconductor Industry Association projections, the number of transistors per chip and the local clock frequencies for high-performance microprocessors will continue to grow exponentially in the near future. Soft errors, caused mainly by cosmic rays and alpha particles from the chip packaging are affecting electronic systems in advanced CMOS technologies. Such reliability issues create tangible risk. Deep submicron process under transient faults caused by soft errors may become the important reasons for chip failure. In this paper, an alternating-complementary self-recovering method based on dual FSMs is proposed, by which the original FSM is decomposed into two sub-FSMs. The two sub-FSMs work by turns and they are indispensably complementary to each other. When an error occurs in one of the two sub-FSMs, a hardware rollback operation will be automatically performed using the correct state in the other sub-FSM. Thus, we can correct the soft error. The method is tested on MCNC91 benchmarks. Experimental results show that compared with published fault-tolerant methods, the average area overhead of the proposed methods is negligible, and the delay decreases dramatically, while it can mask 99.64% soft errors. Hence this method has certain advantages in the performance to tolerate soft error.