Examples relate to predicting wireless access point availability. In one example, a computing device may: generate, for a wireless access point, a mapping for predicting availability of the wireless access point, the mapping specifying: one or more in-range cellular towers to which at least one client device has been connected while the at least one client device was also connected to the wireless access point; one or more border cellular towers to which at least one client device has been connected to i) subsequent to being connected to one of the one or more in-range cellular towers, and ii) while not connected to the wireless access point; and one or more out-of-range cellular towers to which at least one client device has been connected to i) subsequent to being connected to one of the one or more border cellular lowers, and ii) while not connected to the wireless access point.