The subject matter of this specification generally relates to cloud-hosted certificate lifecycle management (CLM) to on-premises certificate authority (CA) communication. In some implementations, a method includes receiving a task request specifying a requested task and an identifier specifying a location for task execution, determining the requested task and that the location for task execution for the requested task is at an on-premises CA device, in response to determining the requested task and that the location of the task is at the on-premises CA device, storing a request task data entry that links the task request to the location for task execution, providing a notification to an on-premises CA gateway, and in response to the notification, providing the requested task for task execution. In some implementations, the remote CA gateway plug-in module maintains a constant communication connection with the on-premises CA gateway via a persistent client-initiated communication protocol.