An apparatus and method for persistent allocation in a wireless communication system are provided. An operation method of a Base Station (BS) includes determining if decoding information for one or more persistent allocations assigned to one or more corresponding Mobile Stations (MSs) is updated, if the decoding information is updated, generating a signaling message to signal the update of the decoding information, and transmitting the signaling message through a DL MAP. The signaling message includes an R_CID and ACID associated with at least one persistent allocation to which the updated decoding information is to be applied.