A method of performing random access in a wireless communication system is disclosed. The method of performing random access in a user equipment of a wireless communication system which uses multiple carriers includes transmitting a preamble for random access to a network, receiving a random access response message from the network in response to the preamble, transmitting a connection setup request message to the network, the connection setup request message requesting connection establishment with the network, and receiving a first message from the network, the first message including connection setup information and contention resolution information in a random access procedure. If a user equipment identifier of the user equipment is included in the message, the user equipment determines that it has successfully performed random access and performs a next procedure in accordance with the connection setup information. If the user equipment identifier of the user equipment is not included in the message, the user equipment determines that it has failed in random access and transmits a random access preamble to the network again after the lapse of a predetermined time period.