An apparatus and method for performing handover in a broadband wireless communication system are provided. A communication method includes broadcasting, by a Base Station (BS), a neighbor advertisement message including neighbor cell information through each Frequency Allocation (FA); analyzing the neighbor cell advertise message by a plurality of Media Access Control (MAC) processors of an Mobile Station (MS) to obtain FA configuration information of each neighbor cell; independently determining handover by the MAC processors of the MS; generating the start of handover by one MAC which first determines handover; and determining a handover target by the remaining MAC processors so that handover is performed to different FAs of the same BS of the MAC processor which generates the start of handover by using the FA configuration information of each neighbor cell.