A non-transitory computer-readable recording medium having stored therein a communication control program for causing a computer to execute a process includes: receiving, from each of a plurality of base stations, communication result between the respective base stations and a communication terminal; storing, when the received communication result indicates that transmission of a message from a first base station to a specific communication terminal is failed, the message in a storage in association with identification information on the specific communication terminal; and referring, when the received communication results indicates that communication is established between a second base station and the specific communication terminal, to the storage, transmitting the message stored in association with the identification information on the specific communication terminal to the second base station, and requesting the second base station to transmit the message to the specific communication terminal.