Fair exchange protocol is an important security protocol in E-commerce.A certificateless verifiably encrypted signature scheme is constructed based on certificateless cryptosystem.And based on verifiably encrypted signature scheme,a new certificateless fair exchange protocol is designed.The proposed protocol reduces the cost of the key-escrow and certificate management,and meets the validity,fairness,timeliness and optimization.