An implantable medical device (IMD) having a rechargeable and primary battery is disclosed, as are algorithms for automatically selecting use of these batteries at particular times. In one IMD embodiment, the primary battery acts as the main battery, and an algorithm allows the IMD to draw power from the primary battery until its voltage reaches a threshold, after which the algorithm allows the IMD to draw power from the rechargeable battery when it is sufficiently charged. In another IMD embodiment, the rechargeable battery acts as the main battery, and an algorithm allows the IMD to draw power from the rechargeable battery if it is sufficiently charged; otherwise, the algorithm allows the IMD to draw power from the primary battery. Further disclosed are techniques for telemetering data relevant to both batteries to an external device, and for allowing a patient to choose use of a particular one of the batteries.