In a method of configuring connection identifier (CID) update information in a broadband wireless access (BWA) communication system where each service between an mobile station (MS) and a base station (BS) has a unique CID, a registration request message is received from the MS, requesting updating of at least one old CID used for the MS. The CID update information is configured to include a bitmap area indicating whether a service corresponding to the at least one old CID is available, and a new CID area including at least one new CID in correspondence with a predetermined bit value in the bitmap area.