Tampering, forgery and theft of the measurement and control messages in a smart grid could cause one breakdown in the power system. However, no security measures are employed for communications in intelligent substations. Communication services in an intelligent substation have high demands for real-time performance, which must be considered when deploying security measures. This paper studies the security requirements of communication services in intelligent substations, analyzes the security capabilities and shortages of IEC 62351, and proposes a novel security scheme for intelligent substation communications. This security scheme covers internal and telecontrol communications, in which the real-time performance of each security measure is considered. In this scheme, certificateless public key cryptography (CLPKC) is used to avoid the latency of certificate exchange in certificate-based cryptosystem and the problem of key escrow in identity-based cryptosystem; the security measures of generic object-oriented substation event, sampled measure value and manufacturing message specification in IEC 62351 are improved to meet the real-time requirements of the messages as well as to provide new security features to resist repudiation and replay attacks; and the security at transport layer is modified to fit CLPKC, which implements mutual authentication by exchanging signatures. Furthermore, a deployment of CLPKC in an intelligent substation is presented. We also evaluate the security properties of the scheme and analyze the end-to-end delays of secured services by combining theoretical calculation and simulation in this paper. The results indicate that the proposed scheme meets the requirements of security and real-time performance of communications in intelligent substations.