Methods and apparatus for multiple user uplink are provided. In one aspect, a method of transmitting a physical layer convergence protocol data unit on a wireless medium includes generating a first portion and a second portion of the physical layer convergence protocol data unit, transmitting the first portion at a first data rate, the first portion decodable by a first and second sets of devices, and transmitting the second portion at a second data rate higher than the first data rate, the second portion decodable by the second set of devices.