A network connection method and apparatus for improving network connection performance of a mobile station in a Broadband Wireless Access (BWA) system is provided. A network connection method of the present invention includes checking whether a cell change from a first cell to a second cell is detected while waiting for a network connection request message, after an acquisition of a synchronization with a first base station associated with the first cell, determining, if the cell change is detected, whether a synchronization is acquired with a second base station associated with the second cell and whether the network connection request message is detected, initiating, if the network connection request message is detected after the synchronization is acquired with the second base station, a network entry procedure, saving, if the network connection request message is detected before the synchronization is acquired with the second base station, the network connection request message in a buffer, and initiating, if the synchronization is acquired with the second base station after saving the network connection request message, a network entry procedure using the network connection request message saved in the buffer.