An apparatus and method for determining operation of location update in a broadband wireless communication system are provided. The apparatus includes a receiver, an interpreter, and a determiner. In an idle mode, the receiver receives a paging advertisement message from a Base Station (BS). The interpreter identifies paging group identification information included in the paging advertisement message. The determiner determines one of execution and non-execution of a location update process due to a change of a paging group if the paging group identification information is different from paging group identification information included in a previously received paging advertisement message.