A system for verifying an association between an application and a mobile computing device. The mobile computing device transmits a request to a service to verify the application, which has an application instance identifier. A mobile device identifier, used to establish a communication channel with the mobile computing device, is also conveyed to the service. The mobile computing device receives one or more telephone call setup messages directed to the mobile device identifier, each of which signal a voice call request, and provides an indication to the service of the receipt of the telephone call setup messages. In response to receiving the indication, the service establishes an association between the application instance identifier and the mobile device identifier.
