A method and apparatus of a base station (BS) perform uplink (UL) random access in a wireless communication system. Random access channel information is determined on each of a plurality of frames constituting a superframe, and a control message comprising the random access channel information is broadcasted. A method and apparatus of a mobile station (MS) perform UL random access in a wireless communication system. A control message comprising random access channel information is received. A frame for minimizing a collision during a contention-based random access is selected based on the random access channel information. For data to be transmitted using the selected frame, it is determined whether the information to be transmitted is an access class with equal or higher priority to a received access class comprised in the random access channel information. A contention-based random access bandwidth request is transmitted to the BS for the data to be transmitted.