Anonymizing location information of a mobile device by an anonymization provider. The anonymization provider receives, from the mobile device, location information identifying the location of the mobile device and anonymity requirements. The anonymization provider determines whether the received location information satisfies the received anonymity requirements. Based on the received location information satisfying the received anonymity requirements, the anonymization provider generates an obfuscated location for the mobile device and sends the obfuscated location to the mobile device. Based on the received location information not satisfying the received anonymity requirements, the anonymization provider sends a request for new anonymity requirements to the mobile device.