Over-discharge is one of the most common electrical abuses a Li-ion battery suffers. This paper presents preliminary results for the failure signatures of over-discharged Li-ion batteries, and proposes a rule-based method and a probabilistic method for failure detection. The two methods are verified using experimental results for a Li-ion battery. The proposed methods were successfully implemented in a real-time system for failure detection and early warning.