A system for verifying an association between an application and a mobile computing device. The application is identified by an application instance identifier, which uniquely identifies the instance of the application on the mobile computing device. The system receives a request to verify the application, including the application instance identifier. The system also obtains a mobile device identifier used to communicate with the mobile computing device. The system initiates one or more telephone call setup messages, which signal a voice call request, to the mobile computing device using the mobile device identifier. Based on receiving an indication that the one or more telephone call setup messages were detected at the mobile computing device, the system associates the application instance identifier with the mobile device identifier.