A method and apparatus for updating an anti-replay window in Internet Protocol Security (IPSec). The method includes determining whether a difference between a sequence number extracted from a received packet and a maximum value of a sequence number of an anti-replay window is greater than a predetermined value; if it is determined that the difference is greater than the predetermined value, creating a first bit map based on a size of the anti-replay window and a second bit map based on the sequence number extracted from the received packet, respectively; comparing the number of bit values in the first bit map of packets received during a predetermined time with the number of bit values in the second bit map of packets received during the predetermined time, and updating the anti-replay window.