"Contract first" involves creating the WSDL first and then using that to generate the code. There aren't many tools to do this.
Essentially, this approach involves modelling the messages, data and interfaces at the start and then publishing them as a contract before coding the implementation begins. Typically, modelling of the data and messages is done using a XML Schema (i.e. XSD files) and the contract is formalised using the Web Services Description Language (WSDL files).
thinktecture offer their free tool to do this which is nicely integrated with Visual Studio (2003 and 2005) and also allows a command line interface.
Get it from here.
Documentation and walk-through here.
Two MSDN articles which cover this are: