Implementations for resilient scheduling of broker jobs for asynchronous tasks in a multi-tenant Platform-as-a-Service (PaaS) system are disclosed. A method of the disclosure includes receiving, by the processing device of a broker of a multi-tenant PaaS system from a user of the multi-tenant PaaS system, a request to complete a job, adding, by the processing device, an entry corresponding to the requested job in a data store of the broker, adding, by the processing device, another entry corresponding to the requested job in a scheduler communicably coupled to the broker, and sending, by the processing device to the user, an acknowledgment of the request and an identifier (ID) of the job, wherein the job is processed asynchronous to the sending of the acknowledgment.