Se vuoi puoi usare un thread, oppure puoi usare la chiamata asincrona. Ecco un esempio:
private void Test()
{
    MioServizioReference.MioServizioSoapClient service = 
       new MioServizioReference.MioServizioSoapClient();
    service.MioMetodoCompleted += 
       new EventHandler<MioServizioReference.MioMetodoCompletedEventArgs>(MioMetodoComplete);
    service.MioMetodoAsync();
}
private void MioMetodoComplete(object sender, MioServizioReference.MioMetodoCompletedEventArgs e)
{
    if (e.Error == null)
        textBox1.Text = e.Result;
}
Come vedi il codice che è stato generato contiene un mucchio di wrapper attorno ai metodi del Web Service (MioMetodoCompleted, MioMetodoAsync, MioMetodoCompletedEventArgs), all' inizio si rimane un po spaesati, ma non è poi cosi complicato.