I've had this a few times in minus 40 with an old battery. I had to bring it inside once and warm it up then put it on the charger. You can try to keep starting it at some point she seems to just start. If you're going to replace anything, start with the battery.