An apparatus and a method for reallocating segments in a broadband wireless communication system are provided. An average density for all cells in system and an average minimal inter-cell distance R are computed. A circle is determined having a radius kR and a center at a corresponding cell by increasing a constant k until a density of the circle becomes less than or equal to the average density. A cluster is generated for each cell, which is composed of cells included in the determined circle. Accordingly, segment allocation capability can be improved while minimizing a width of segment reallocation.