This paper presents a systematic study of early stopping criteria for Turbo decoding. First, statistical analysis is carried out on numerous hard/soft variables that may be used in an early stopping criterion. Desirable variables are suggested based on their statistical properties. Simulation results show that any stopping criteria based on a single variable will have BER/FER performance loss. Two criteria, each of which uses two variables, are recommended in this paper and neither of them will result in any performance loss. It is also shown in this paper that the thresholds for these variables should be set to be proportional to the logarithm of the block size instead of being proportional to the block size.