In this paper, we propose the first provable secure certificate-based proxy signature (CBPS) with message recovery without bilinear pairing. In 2003, Gentry introduced the concept of certificate-based cryptography to solve certificate management and key escrow problems in public key infrastructure and identity-based cryptosystems, respectively. Because the overall cost of pairing computation is higher than scalar multiplication (e.g., over elliptic curve group), consequently, the CBPS schemes without pairings would be more efficient. According to the available research in this regard, our scheme is the first provable secure CBPS scheme with message recovery that is based on the elliptic curve discrete logarithm problem. We prove the security of the presented scheme in the random oracle model against existential forgery under adaptive chosen message and ID attacks. Moreover, the paper will also show how it would be possible to convert this scheme to the CBPS scheme without message recovery. This scheme has more applications in cases with constrain power and restricted bandwidth. Copyright (C) 2016 John Wiley & Sons, Ltd.