A method and an apparatus for requesting Uplink (UL) resource allocation in a beamforming-based wireless communication system are provided. A Mobile Station (MS) acquires UL beam pair information indicating a best MS transmit beam and a best Base Station (BS) receive beam for UL transmission, determines a best BS transmit beam for Downlink (DL) reception, selects a Bandwidth Request (BR) code and a BR channel from available BR codes and a designated BR transmit resource, wherein at least one of the BR code and the BR channel is mapped to at least one of the best BS receive beam and the best BS transmit beam, and transmits the selected BR code to a BS over the selected BR channel. The BS allocates a UL resource for transmission of a BR message and UL data considering the best BS receive beam.