A wireless device and a random access method thereof for a mobile communication system are provided. The mobile communication system defines a plurality of preambles. The wireless device receives a system message carrying a random access success rate from a base station, and divides the preambles into N preamble subsets according to the random access success rate. The N preamble subsets have a strict partial order relationship therebetween. The union of the N preamble subsets consists of the preambles. When requesting random access from the base station, the wireless device randomly selects a preamble from the smallest preamble subset. When a preamble collision occurs, the wireless device reselects a preamble from the larger preamble subset gradually for the random access.