A handover method and system in a communication system. In the method, a serving Base Station (BS) broadcasts neighbor BS information including BS identifiers and preamble indices of a plurality of neighbor BSs, receives a handover request message from a Mobile Station (MS), the handover request message including a first set of at least one BS identifier and at least one preamble index for at least one neighbor BS among the plurality of neighbor BSs, and transmits a handover response message to the MS, the handover response message including a second set of at least one BS identifier and at least one preamble index for at least one recommended neighbor BS.