.NET 4.0 doesn't have a WebService template, so you have to use .NET 3.5 or earlier version.
Steps:
1. File > New Project...
2. Change the Framework version to ".NET Framework 3.5".
3. Select the Language Visual C# (expand the node if not already), choose Web and the select "ASP .NET Web Service Application"
You will see a WebService code template:
