Rechargeable batteries are critical components in many electrical systems nowadays. One has to ensure reliable diagnosis and assessment of the installed batteries for smooth and safe operations. Assessment of the remaining capacity of a battery is crucial diagnostic information. A battery management system (BMS) needs to reliably report the ability of the battery to supply power or the lack thereof. If the BMS fails to do so at an early stage, this may compromise the health of the entire electric system. When a battery nears a region where the battery state-of-charge (SOC) is low, there is a risk of an abrupt drop in the terminal voltage. An early detection of such a region is crucial; otherwise, the BMS may not have enough time to react. To address this issue, our work provides a novel supervised learning approach towards an early detection of Li-ion battery terminal voltage collapse. No knowledge of initial SOC or battery model parameters is required. This is particularly important as batteries lose their capacity to store charge over time. The efficacy of the proposed approach is demonstrated by an early and accurate detection of terminal voltage collapse over a set of discharge tests conducted using multiple batteries.