Nowadays, Web services are the leading solution for solving the problem of information systems’ integration. Web services are based on the service oriented architecture (SOA). Preserving privacy of web services is one of the main challenges during their interaction. Therefore, minimizing the number of the disclosed credentials that are required for accessing the web services resources during the interaction is a desirable behavior. Credentials generalization and substitution and credentials encryption can be used for privacy preserving. To the best of our knowledge, in the current privacy preserving approaches for web services, there is no technique that uses the negotiation for credential generalization and substitution between the consumer and the provider in conjunction with the credentials encryption using certificate authority as a third party. In this paper, a proposed approach for web services privacy preserving is proposed. This approach is based on the negotiation, encryption, and certificate authorities as third parties. The proposed approach is implemented and tested. The results show that the number of disclosed sensitive credential is the minimum number of credentials that can be disclosed to guarantee the accessing of the service.