Mechanisms enabling link-budget-limited (LBL) devices to more effectively perform random access may include: (1) broadcasting a Physical Random Access Channel (PRACH) configuration index (PCI) reserved for LBL devices; (2) configuring LBL devices to use a PCI that is offset from the conventional PCI of current cell; (3) configuring LBL devices to transmit PRACH messages using an alternative set of subframes, different from conventionally-defined subframe set; (4) configuring LBL devices to transmit PRACH messages on odd frames when the conventional PRACH configuration specifies even frames; (5) configuring LBL devices to generate and use extra PRACH preambles that are not used by non-LBL devices; (6) configuring LBL devices to use group B preambles while non-LBL devices are configured to use group A preambles; and (7) boosting power of a random access response message after an Nth random access failure with preamble conforming to an LBL-reserved pattern of preambles.