Web service policies capture the capabilities and requirements of Web services from both functional and nonfunctional perspectives. Policies of a Web service govern and ensure the runtime consistency of the service, i.e., people or services interacting with this service are only allowed to perform legitimate actions. When composing Web services, policies of the participated Web services have to be compatible in order to make sensible compositions. Unfortunately, due to heterogeneity of policy specification languages, it is difficult to compare policies of different Web services directly. In this paper, we propose an approach for compatibility checking of Web service policies specified in difference languages. In particular, our approach applies the model-oriented specification from the Vienna Development Method (VDM++). An executable formal model of policy languages is represented in VDM++ and different policies are then translated to this VDM++ model for compatibility checking. Our approach has been validated by a prototype with different Web service policy languages such as WSPL and WS-Policy. © 2009 IEEE.