Provided are an apparatus and method for managing connection identifiers (CIDs) in a multi-hop relay Broadband Wireless Access (BWA) system. An apparatus is provided for a Relay Station (RS) in a multi-hop relay cellular communication system. The apparatus includes a database, a controller, and a transmitter. The database is used for managing a Connection Identifier (CID) set assigned to the RS by a Base Station (BS). The controller accesses the database to assign one CID of the CID set to a Mobile Station (MS) when receiving a control message from the MS. The transmitter constructs a response message including the CID assigned to the MS and transmits the response message to the MS. The MS can be assigned a CID directly from the RS in a condition that the BS is not involved, so that the initial ranging procedure can be rapidly performed.