An inter-cell interference coordination method and apparatus is provided for mitigating inter-cell interference in a wireless communication system by using interference coordination information exchanged among neighbor base stations. The method includes receiving, at a serving base station, power control messages transmitted by neighbor base stations, receiving incoming interference coordination messages transmitted by neighbor base stations, each message including interference indicators of resource blocks, allocating the resource blocks with transmission power per resource block to user equipments served by the base station based on the power control and interference coordination messages, generating outgoing interference coordination messages for the respective neighbor base stations based on the resource block allocation result, and transmitting the interference coordination messages to the neighbor base stations, respectively.