A method is provided for performing an authentication procedure according to location registration and update for a mobile subscriber station (MSS) in a broadband wireless access (BWA) communication system. The system includes the MSS operating in idle mode to minimize power consumption, paging groups each being formed by a plurality of adjacent cells in which a plurality of MSSs are paged, base stations (BSs) for paging the plurality of MSSs within each paging group, and a server for controlling location registration and authentication for the plurality of MSSs. The server determines whether to approve a request for transition to the idle mode received from the MSS through a BS. If the server approves the request for the transition to the idle mode, it allocates authentication information to the MSS through the BS and registers location of the MSS. When it is determined that the MSS has moved to a different paging group, the MSS sends a location update request including a resulting value computed using the authentication information allocated from the server. The server authenticates the MSS according to the authentication information included in the location update request and registers the changed location of the MSS authenticated successfully.