Pair watch with new phone after stolen old

Setup your Watch to a new iPhone

And start at the section "if you don't have your old phone"

When you unpair your watch a backup of your health and fitness data is made automatically as long as the paired phone is signed into iCloud and the backup is uploaded to icloud,when you come to re-pair your watch you are asked if you want to set it it up as new or restore it from a backup,you choose restore from backup then all your health and fitness data is downloaded back to the phone and watch from the icloud backup and you carry on using your watch with all previous data intact.