The state of power (SOP) refers to the maximum available power from a battery. The SOP is a function of the open circuit voltage and internal resistance of the battery, both of which change with the state of charge (SOC). As such, the SOP is a more informative metric of battery state than the SOC and is crucial for the continued operation of an electric vehicle. The existing approaches employ non-linear system identification techniques that are sensitive to changes along temperature and SOC. In this paper, a novel approach is proposed to estimate the state of power in real time. The proposed approach does not require non-linear approaches for both system identification and filtering. Instead, a linear least squares estimation technique is utilized to estimate the parameters needed for SOP computation. The proposed approach utilizes a mechanism to account for the change in OCV in the observation window and employs a simple yet robust technique to account for the relaxation effect of the battery. The SOP estimates computed through the proposed approach are tested using realistic battery data collected from three battery cells at the following eight different temperatures: −25◦C, −15◦C, −5 ◦C, 5 ◦C, 15◦C, 25◦C, 35◦C, and 45◦C.