A radio communication system including a radio communication device configured to request connection, and radio relay devices. The communication device includes a neighbor node discovery unit to transmit a neighbor node discovery message, a selection unit to select the connection destination based on determination information when a response message to the discovery message is received, the determination information being used for determining whether to select a transmission source as the connection destination, and a storage unit to store the determination information. Each relay device includes a calculation processing unit to calculate, in accordance with a value of the determination information, transmission waiting time until transmission of the response message, a timer unit to manage passage of the waiting time, a response message transmission unit to transmit the response message when the timer unit notifies elapse of the waiting time, and a storage unit configured to store the determination information.