Enhanced random access procedures for link-budget-limited user equipment (UE) devices are disclosed. A user equipment device may transmit a first message containing a Physical Random Access Channel (PRACH). The PRACH contains instances of a Zadoff-Chu sequence, and may be transmitted repeatedly as part of a single random attempt, to facilitate correlation data combining at the base station. The available Zadoff-Chu sequences may be partitioned among a plurality of sets, each set being associated with a respective Doppler shift range (or frequency hop pattern or time repetition pattern). A UE device may signal Doppler shift (or other information) to the base station by selection of one of the sets. The first PRACH transmission and the following PRACH transmission may occur in consecutive subframes. A UE device may select from a special set of Zadoff-Chu sequences (different from a conventional set of sequences), to signal its status as a link-budget-limited device.