An apparatus and method for reducing MAP channel overhead in a broadband wireless communication system. In a Base Station (BS), a traffic classifier classifies transmission data into a first group and a second group according to user channel information and packet sizes of the transmission data. A MAP channel configure configures a MAP channel to include information about users of the first group and positions of data for the users, information indicating whether users of the second group have succeeded in random access in a second uplink data region of a previous frame, and information about resource reservation for a current frame for the second group. A channel mapper maps the first group to a first downlink data region and maps the second group to a second downlink data region according to the MAP channel.