To adaptively determine a Tx beam subset for random access in a wireless communication system, a method for operating a Mobile Station (MS) includes determining at least one beam subset which satisfies a predefined condition, among a plurality of beam subsets, and transmitting random access preambles using Tx beams of the at least one beam subset. An MS in a wireless communication system includes a controller configured to determine at least one beam subset that satisfies a condition, among a plurality of beam subsets, and a transmitter configured to transmit random access preambles using Transmit (Tx) beams of the at least one beam subset, wherein the plurality of the beam subsets each comprise a plurality of beams radiating to different directions from one another. Other embodiments including a base station and a mobile station are also disclosed.