A method for transmitting a signal on a bandwidth request channel, a mobile station apparatus using the same, a method for performing a bandwidth request procedure in relation to a bandwidth request from a mobile station, and a base station apparatus using the same are disclosed. A mobile station transmits a bandwidth request preamble and a bandwidth request message together to a base station to request a bandwidth. A region of the bandwidth request message may be configured as null tones. In response to the bandwidth request of the mobile station, the base station transmits a BR ACK A-MAP IE indicating reception of the bandwidth request to the mobile station in response to the bandwidth request. The base station transmits an uplink grant to the mobile station by a BR ACK A-MAP IE or a CDMA allocation A-MAP IE. Upon receipt of the uplink grant from the base station, the mobile station transmits uplink scheduled data to the base station. However, if the base station fails to decode the quick access message or the region of the quick access message is filled with null tones, the base station transmits a grant for a bandwidth request header to the mobile station, instead of an uplink grant.