Electric vehicle (EV) power demands come from its acceleration/braking as well as consumptions of the components. The power delivered to meet any demand is limited to the available power of the battery. This makes the battery state of available power (SoAP) a critical variable for battery management purposes. This paper presents a novel approach for long-term SoAP prediction by supervising the working conditions for prediction of future load. Firstly, a battery equivalent circuit model (ECM) coupled with a thermal model is established to accurately capture the battery dynamics. The battery model is then connected to an EV model in order to interpret the working conditions to battery power demand. By supervising the historical usage conditions, a long-term load prediction mechanism is designed based on wavelet analysis and Markov models. This facilitates the separation of low and high frequency load demands and addresses future uncertainties. Finally, the SoAP prediction is put forward along with a sensitivity analysis with respect to battery model and load prediction mechanism parameters. It is demonstrated that compared to the existing approaches for load and SoAP prediction, the developed method is more practical and accurate. Co-simulations via MATLAB and AMESim as well as experiments on a set of commercially available Lithium-ion (Li-ion) cylindrical cells under real-world drive cycles prove the given concept and validate the performance of the method.