Business protocols are becoming a necessary part ofWeb services description [4]. The work presented in [4] investigates mechanisms for analyzing the compatibility and the substitution (i.e., replaceability) of Web services based on their functional properties. In this paper, we focus on the replaceability analysis.Whether a service can replace another depends not only on their functional properties but also on non functional requirements (e.g., privacy policies). We propose a privacy-aware protocol replaceability approach to extend the work presented in [4] by privacy properties. We introduce a rule-based privacy model and we extend business protocols, leading to what we call private business protocols. Finally, a private replaceability analysis of private business protocols is discussed. We mainly investigate compatibility issues, that is whether one private business protocol can support the same set of conversations with respect to the privacy requirements.