An apparatus and method for allocating Radio Network Temporary Identifiers (RNTIs) for random access in a mobile communication system are provided. An Evolved Node B (ENB) determines the number of RNTIs allocated to at least one User Equipment (UE) that transmitted a random access preamble, determines an average number of random access preambles received during a Transmission Time Interval (TTI), and sets a timer based on the number of allocated RNTIs and the average number of random access preambles. If a cell identifier corresponding to a first UE is not received from an upper layer before expiration of the timer, the ENB releases the RNTI allocated to the first UE, and allocates the released RNTI to a second UE different from the first UE.