A method for establishing a connection with a generic access network (GAN) and an associated GAN-enabled mobile station are provided. The method is used in the GAN-enabled mobile station. The method first issues a request message to the generic access network to request for connection establishment, and at the same time starts a timer with a timeout longer than five seconds. Then, the method determines a state of the GAN-enabled mobile station according to a response message corresponding to the request message when the response message is received within the timeout. In this manner, the GAN-enabled mobile station can increase the success rate of connection establishment with the generic access network.