A Random Access method in a telecommunication system, includes the steps of: receiving two or more identical preambles transmitted from two or more User Equipments (UEs), respectively; determining a minimum difference between the two or more identical preambles in a given domain; transmitting a response message to each of the two or more UEs; and receiving a connection setup message using information included in the respective response messages transmitted to each of the two or more UEs.