A communications device for communicating via a mobile communications network, the mobile communications network including one or more network elements providing a wireless access interface for transmitting signals to or receiving signals from the communications device, the communications device comprising: a transmitter configured to transmit the signals to the mobile communications network via the wireless access interface provided by the one or more network elements of the mobile communications network, and a receiver configured to receive the signals from the mobile communications network via the wireless access interface provided by the one or more network elements of the mobile communications network, and a controller configured to control the transmitter to transmit a random access message to a first network element via a random access channel of the wireless access interface which is common to one or more other communications devices, to receive from the first network element an acknowledgement in response to the random access message providing an indication of an allocation of communications resources of a shared uplink channel for the communications device to transmit signals to the first network element or a negative acknowledgement providing an indication that the communications device has not been allocated communications resources of the shared up-link channel, wherein in response to detection of a first random access failure condition by the controller, the controller is configured in combination with the transmitter to retransmit the random access message one or more times (506, 507), each retransmission of the random access message being after a variable delay which is greater than or equal to the delay of a previous retransmission and each retransmission of the random access message being transmitted with an increased power to a previous retransmission, and in response to detection of a second random access failure condition different to the first random access failure condition by the controller, the controller is configured in combination with the transmitter to select a second network element to which to transmit a subsequent random access message, the second network element having been selected in accordance with a network element selection or reselection criterion. a transmitter configured to transmit the signals to the mobile communications network via the wireless access interface provided by the one or more network elements of the mobile communications network, and a receiver configured to receive the signals from the mobile communications network via the wireless access interface provided by the one or more network elements of the mobile communications network, and a controller configured to control the transmitter to transmit a random access message to a first network element via a random access channel of the wireless access interface which is common to one or more other communications devices, to receive from the first network element an acknowledgement in response to the random access message providing an indication of an allocation of communications resources of a shared uplink channel for the communications device to transmit signals to the first network element or a negative acknowledgement providing an indication that the communications device has not been allocated communications resources of the shared up-link channel, wherein in response to detection of a first random access failure condition by the controller, the controller is configured in combination with the transmitter to retransmit the random access message one or more times (506, 507), each retransmission of the random access message being after a variable delay which is greater than or equal to the delay of a previous retransmission and each retransmission of the random access message being transmitted with an increased power to a previous retransmission, and in response to detection of a second random access failure condition different to the first random access failure condition by the controller, the controller is configured in combination with the transmitter to select a second network element to which to transmit a subsequent random access message, the second network element having been selected in accordance with a network element selection or reselection criterion.