In this paper, we propose a novel way of modeling web services using folksonomies. The key advantage of our model is that it allows a large number of users to participate, easily, in annotating services with tags. This is in contrast to more expressive, logic based models of services, such as Semantic Web Service models, which require significant expertise for annotation and maintenance. Our folksonomy-based model allows associating semantic constraints on the input and output messages of web service operations using tags obtained from a folksonomy. We show how the model can be used for discovery and composition of services. We also describe a planner that uses this model to compose services and create workflows, automatically. We present performance results for the planner and our experiences in using this model in a sample real-world domain.