A wireless device and a method therein for performing a transmission at a changed Coverage Enhancement (CE) level in a random access procedure. The wireless device receives a random access order indicating a first preamble and a first carrier. Further, the wireless device transmits, to a network node, the first preamble on the first carrier using a first CE level. In the absence of a valid response after a number of transmissions, the wireless device determines a second CE level that is different from the first CE level. Thereafter, the wireless device selects, in a predictable way for the network node, a carrier that is supporting the second CE level, and transmits, to the network node, a preamble on the carrier using the second CE level.