Addressing the reuse of lithium ion batteries (LIBs) extracted from used battery packs is an option for addressing environmental concerns. To guarantee their safety, the development of non-destructive analysis to identify LIBs exposed to over-discharge is mandatory. In this study, over-discharge-induced degradation in graphite/nickel cobalt aluminum oxide (NCA) lithium ion cells was investigated using differential voltage analysis (DVA) and electrochemical impedance spectroscopy (EIS). Two-stage cell capacity decay was solely observed in the deep over-discharge cycling at a lower cutoff voltage (LCV) of 1.00 V; in the first stage, the capacity gradually decreased similar to that at LCV >= 2.50 V, and then decreased steeply. In the over-discharge cycling, the DVA results confirmed that the electrode balancing between the anode and cathode contribute to increasing the cell capacity, whereas the cathode capacity decreased as cycling progressed, suggesting that electrode degradation induced by over-discharge is difficult to assess using the cell capacities. EIS analysis revealed that the charge-transfer resistance and interfacial capacitance of the NCA cathode changed markedly in the first stage under over-discharge. This study reports a meticulous characterization of over-discharge of LIBs using non-destructive electrochemical analysis and introduces a critical aspect for their detection before serious cell deterioration.