A method and a wireless device (110) for managing probe messages are disclosed. The probe messages are used for verifying a required level of a connectivity for a service of the wireless device (110) towards a wireless network (100). The required level of the connectivity relates to likelihood of maintaining the connectivity towards the wireless network (100). The wireless device (110) estimates an estimated level of the connectivity for the wireless device (110). The wireless device (110) further adjusts an amount of the probe messages based on the required level of the connectivity and the estimated level of the connectivity. Moreover, corresponding computer programs and computer program products are disclosed.