An advertising algorithm is disclosed which operates in an Implantable Medical Device (IMD) to adjust an interval at which the IMD will transmit advertising data packets to an external device able to connect with the IMD. When a communication session between the IMD and an external device is terminated, the advertising algorithm will issue advertising data packets at a higher rate for a set duration. This will allow the external device to connect more quickly with the IMD in a next communication session. After the set duration, when it may be assumed that the external device is less likely to connect with the IMD, the algorithm reduces that rate at which advertising data packets are issued, which saves power in the IMD.