We study the nature of excess electrons in CsPbBr3 and identify several single and double polaronic states. We emphasize the importance of proper inclusion of the self-interaction corrections for the stability of small electron polarons in this material. We demonstrate that spin-orbit coupling (SOC) has a significant impact on the energetics of the polaronic states. In particular, we find that SOC disfavors electron localization and leads to different polaronic geometries. Additionally, by carrying out thermodynamic integration, we show that small electron polarons are thermally stabilized in CsPbBr3. The small energy differences between the localized and delocalized electronic states could possibly reconcile the apparently conflicting properties of high charge-carrier mobilities and low recombinations rates.