This paper studies proxy signatures in the newly proposed certificateless public key setting. The authorspresent a very strong security model for certificateless proxy signature schemes against both Super Type IAdversary and Super Type II Adversary. And also an efficient construction of certificateless proxy signature schemeusing bilinear maps is put forward. The security of this scheme is based on the infeasibility of the ComputationalDiffie-Hellman problem and is formally proven under the security model of certificateless proxy signature schemes.Due to its security, high efficiency and freedom from certificate management, it may have practical applications inelectronic commerce and mobile agent systems, etc.