An apparatus and a method for handover in a broadband wireless communication system supporting a Mobile Relay Station (MRS) are provided. The method includes transmitting a Connection ID (CID) of Mobile Stations (MSs), the CIDs pre-allocated by a target BS, to the MSs; sending a resource allocation message comprising uplink resource allocation information for bandwidth request of the MSs, to the MSs; receiving a bandwidth request message which comprises security authentication information of each MS, from the MSs using an uplink resource allocated through the uplink resource allocation information; and aggregating bandwidth request messages of the MSs and sending a ranging request message comprising the security authentication information and bandwidth request information of the MSs to the target BS. Thus, the handover delay time, which is inevitable for the bandwidth request in the conventional connection set-up procedure, can be reduced, and the handover with the reliability guaranteed can be achieved by allowing the security related processing in the network re-entry procedure.