A radio communication terminal device includes a storage unit that stores group information indicating a group of frequencies belonging to the same communication carrier, a communication-carrier searching unit that selects one of to-be-selected frequencies, the to-be-selected frequencies being frequencies at which radio waves arrive, and that searches for a communication carrier using the selected frequency on a basis of identification information received at the selected frequency, and a search-execution controlling unit that excludes, from the to-be-selected frequencies, another frequency that belongs to the group information including the selected frequency and that is other than the selected frequency.