A radio communication system includes a radio base station and a terminal device. The radio base station and the terminal device share correspondence information about subsets of preamble sequences obtained by segmenting preamble sequences available in the radio communication systems into groups, each of the subsets being associated with a received signal level at the terminal device and a number of repetitions for transmitting the preamble sequences of each of the subsets. Based upon a receive level of a signal transmitted from the radio base station, the terminal device selects a subset corresponding to the receive level by referring to the correspondence information and transmits a preamble sequence included in the selected subset at the number of repetitions associated with the selected subset.