Abstract The application of digital signature technology on the Internet of Vehicles (IoV) is affected by its network and communication environment, which requires low transmission delay, power consumption, and highsecurity requirement. To the best of our knowledge, a well-designed solution that uses signcryption technology has not been proposed in the IoV research area. Motivated by the fact, a certificateless signcryption scheme based on Elliptic Curve Digital Signature Algorithm, which also considers pseudonym and timestamp mechanism, has been designed in this paper. We prove that our proposed scheme can be reduced to solving the difficulty of the Computational Diffie-Hellman problem under the standard model, show that the scheme meets both security and efficiency requirements, and provides a comparative analysis with the state-of-the-art schemes in terms of security analysis, computational cost, and communication cost, demonstrating that our proposed scheme is suitable to be deployed in the IoV environment.