Disclosed is a random access method for minimizing delay for call setup, managing a random access request conflict, and adaptively allocating uplink radio resources according to the reason of an asynchronous random access from a terminal in an initial random access procedure between a base station and a terminal in a cellular mobile communication system for a packet service. The method begins with a radio resource control (RRC) layer of the terminal transferring a control primitive and an RRC connection request message to a medium access control (MAC) layer of the terminal. The MAC layer of the terminal requests the MAC layer of the base station to allocate a resource for random access. The MAC layer of the base station allocates resources upon the allocation request from the terminal and transfers the resources to the MAC layer of the terminal. The MAC layer of the terminal sets up an uplink sub-channel based on the allocated resources and transfers the RRC connection request message to the MAC layer of the base station through the uplink sub-channel. The MAC layer of the base station analyzes the RRC connection request message and requests the RRC layer of the base station to set up the RRC connection. The MAC layer of the base station transfers an RRC connection setup message to the terminal.