Certificateless public key cryptosystem (CLPKC) is a desirable cryptographic system because it refrains from both certificate management and key escrow. In CLPKC, how to revoke a misbehaving or compromised user is an important issue. However, the existing revocable methods in CLPKC are impractical because of the use of either an expensive mediator or a burdensome key generation center (KGC). In order to overcome this drawback, we introduce outsourcing computation into CLPKC for the first time and design an outsourced revocable certificateless signature (ORCLS) scheme, and the revocation functionality is outsourced to a cloud server. The amount of computation needed to revoke a user is borne by the cloud server, which greatly reduces the burden on the KGC. In the rest of this paper, we formalize the definition and the security model for an ORCLS scheme and construct the first ORCLS scheme without bilinear pairings. It is proved that our scheme is existential unforgeable against adaptive chosen-message attacks from Type I, Type II, Type III, and Type IV adversaries under the elliptic curve discrete logarithm problem. Moreover, our scheme needs less computational cost and communication overhead and thus is more efficient than the other proposed revocable certificateless signature schemes so far.