Embodiments of a master station and method for high-efficiency Wi-Fi (HEW) communication using traveling pilots are generally described herein. In some embodiments, the master station is arranged for communicating with a plurality of HEW and may be configured to transmit, during an initial portion of an HEW control period, a master-sync transmission that includes a multi-device HEW preamble arranged to signal and identify data fields for a plurality of scheduled HEW stations. The master station may transmit during the HEW control period the data fields with traveling pilots to the scheduled HEW stations. The master station may also receive data fields with traveling pilots transmitted by the scheduled HEW stations during the HEW control period. The traveling pilots may comprise pilot signals that are shifted among orthogonal-frequency multiplexed (OFDM) subcarriers during transmission of one or more of the data fields.