Handover apparatus and method using a Relay Node (RN) in a cellular system are provided. The handover method includes receiving, at an RN, broadcast control information of a serving Base Station (BS) and a neighbor BS; network-encoding and broadcasting, at the RN, the received broadcast control information; receiving and storing, at a Mobile Station (MS), the broadcast control information of the serving BS; receiving, at the MS, the network-encoded information from the RN when the MS enters a cell overlapping area; and acquiring, at the MS, the broadcast control information of the neighbor BS by decoding the received network-encoded information with the broadcast control information of the serving BS.