Method and device for discovering a service are provided. A responding device receives a service request frame including a first service identifier indicating a service queried by the requesting device. The responding device transmits a service response frame to indicate that the queried service is currently not available and a service announce frame follows on. The responding device determines whether the queried service is accepted or not during a pre-defined time after transmitting the service response frame.