A system and method for automatic key and certificate management is disclosed. In particular, a key store in a base computer contains both new and previously viewed cryptographic keys. In one embodiment, for each new key, if a corresponding certificate matches an existing certificate, the new certificate may be automatically downloaded to a mobile communications device without prompting a user.