The delivery of paging messages to an access node are delayed based on an estimated paging message load currently being handled by the access node. When a mobility node receives a request that requires a wireless device to be paged, the mobility node refers to an estimate of the current paging load on an access node. This estimate can be based on the number of paging messages that have been sent to the access node that have not elicited a response and have not expired. If the estimated load is less than a threshold amount (e.g., 80%), then the paging message can be sent to the access node without further delay. If the estimated load is greater than the threshold amount, then an amount of time to wait before sending the paging message to the access node is selected or calculated.