Signcryption is a cryptographic primitive that fulfills both the functions of the public key digital signature and the public key encryption in a logical single step, at a cost in the computational and communication significantly lower than that required by the traditional “signature then encryption” approach. Based on discrete logarithm, a new certificateless signcryption scheme without using the bilinear pairings is presented in this paper, and the method to build certificateless signcryption scheme without using the bilinear pairings seems to have never been addressed in the existing literatures. The security analysis of the proposed scheme in the implementation plan with the random oracle model is presented in this paper, and the results show that the proposed scheme is secure on the assumption that the compute Diffle-Hellman problem and the discrete logarithm problem are the difficult problems. The proposed scheme also has the security properties of confidentiality, non-forgeability, publicly verifiability, non-repudiation and perfect forward security, etc. Moreover, the implementation of the proposed scheme only requires three times exponent operations and without any bilinear pairing operation. Compared with other existing certificateless signcryption schemes in the computational complexity, the proposed scheme is more efficient.