Systems and methodologies are described that facilitate a fast access in a wireless communication system, such as OFDMA. According to various aspects, the system and methods are described for generating an access probe comprising an access signature having quality of service information and transmitting the access probe on a random access channel. Also, the system and methods of receiving an access probe, the access probe comprising quality of service information, generating an access grant in response to the receive access probe, addressing the access grant using information from the access probe, and transmitting the access grant.