Methods and apparatuses for association in a beamformed wireless area network (WLAN) are provided. A method for operating a station (STA) includes randomly selecting a plurality of sector sweep frames for association beam transmission within a frame-aligned transmit sector sweep duration in an association beamforming training duration of a beacon interval, transmitting a beam in each of the randomly selected sector sweep frames, and receiving sector sweep feedback from an access point (AP). A method for operating the AP includes receiving at least one transmission from one or more STAs on at least one of randomly selected sector sweep frames within the frame-aligned transmit sector sweep duration, selecting a sector identifier for transmissions from each of the one or more STAs based on the at least one received transmission, and transmitting grouped sector sweep feedback indicating the selected sector identifier for transmissions from each of the one or more STAs.