AbstractCertificateless public key cryptography (PKC) eliminates the use of certificates in traditional PKC and the key escrow problem in identity‐based PKC. Up to now, a number of certificateless proxy signature (CLPS) schemes have been proposed. However, only a little attention has been paid to the construction of CLPS schemes with message recovery. Recently, Singh and Verma proposed a CLPS scheme with message recovery from bilinear pairings. Total computation cost of a pairing is higher than that of elliptic curve‐based scalar multiplication over elliptic curve group. So, schemes without pairings would be more appealing in terms of efficiency. To the best of our knowledge, there is no provable secure CLPS scheme with message recovery based on elliptic curve discrete log problem. We first propose such CLPS scheme. Our scheme is secure against existential forgery under adaptive chosen message and ID attacks. Furthermore, it is more efficient than Singh and Verma's scheme for practical applications. Copyright © 2012 John Wiley & Sons, Ltd.