The disclosed embodiments provide a system that estimates a remaining useful life (RUL) for a fan. During operation, the system receives telemetry data associated with the fan during operation of the critical asset, wherein the telemetry data includes a fan-speed signal. Next, the system uses the telemetry data to construct a historical fan-speed profile, which indicates a cumulative time that the fan has operated in specific ranges of fan speeds. The system then computes an RUL for the fan based on the historical fan-speed profile and empirical time-to-failure (TTF) data, which indicates a TTF for the same type of fan as a function of fan speed. Finally, when the RUL falls below a threshold, the system generates a notification indicating that the fan needs to be replaced.