Web services may be able to publish easily their functions to the rest of the web world. At the same time they suffer by several security pitfalls. Currently, there is limited research on how the proposed web-services security countermeasures affect performance and applicability. In this paper, we introduce the threats/attacks vs. web-services authentication, present the most widely used security method for protecting it, and identify the threats/attacks tackled by those methods. Moreover, we evaluate the web service authentication mechanism proposed in these implementations, not only on a theoretical level (by taking into consideration all the security issues of the implementing authentication sub-mechanisms), but also in a laboratory environment (by conducting extensive experiments). Finally we demonstrate the trade-offs between sophisticated web-service security methods and their performance.