Embodiments of a high-efficiency Wi-Fi (HEW) station, access point (AP), and method for random access contention in a wireless network are generally described herein. In some embodiments, the HEW station may receive a beacon frame that indicates a number of trigger frames (TFs) included in a beacon interval. The beacon frame may be received from an HEW access point (AP) in channel resources that include multiple sub-channels. The HEW station may receive a random access TF that indicates a random access portion of the sub-channels that are allocated for random access contention during an uplink transmission period. The HEW station may select a candidate sub-channel from the channel resources. When the candidate sub-channel is included in the random access portion, the HEW station may transmit an association request (AR) frame on the candidate sub-channel during the uplink transmission period.