A (t,n) threshold signature scheme allows t or more group members to generate signatures on behalf of a group with n members. In contrast to the traditional public key cryptography based on public key infrastructure (PKI) and identity-based public key cryptography (IDPKC), certificateless public key cryptography (CL-PKC) offers useful properties as it does not require any certificates to ensure the authenticity of public keys and the key escrow problem is eliminated. In this paper, we investigate the notion of threshold signature schemes in CL-PKC. We start by pointing out the drawbacks in the two existing certificateless threshold signature schemes. Subsequently, we present an elaborate description of a generic certificateless (t,n) threshold signature scheme with a new security model. The adversaries captured in the new model are more powerful than those considered in the existing schemes. Furthermore, we establish the simulatability for certificateless threshold signature schemes and prove the relationship between the security of certificateless threshold signature schemes and that of the underlying non-threshold certificateless signature schemes. As an instantiation, we present a concrete certificateless threshold signature scheme based on bilinear maps using the techniques of verifiable secret sharing and distributed key generation. The proposed scheme is shown to be existentially unforgeable against adaptively chosen message attacks assuming the hardness of Computational Diffie– Hellman (CDH) problem.