I wasted many hours trying most of the remedies in this thread. I was trying to get a new Series 6 apple watch to pair with my iPhone X Max. I have an AT&T Router that has both a 2.4 GHz and 5 GHz WIFI networks. It is configured by default to put these both on the same SSID and then dynamically route each connecting device to the appropriate network ("band steering"). What finally worked for me was this turning OFF the 5ghz WIFI network in order to force the Apple Watch software update to be downloaded off the 2.4 GHz network. Here's my theory on the problem: The iPhone and the Apple Watch find each other via Bluetooth You start the pairing process The iPhone says, "Hey Watch - you gotta download this 2 GB software update, use this WIFI connection to download it" The Watch gets cross ways when routed to the 5 GHz network. The Series 6 Apple Watch is supposed to support 5 GHz WIFI networks, but this was definitely the culprit for me. It's possible that the band steering feature from the AT&T Router jacks up the initial connection, or it's possible that the Patch download code has to work on both older and newer Apple Watches and has something that doesn't play nice with a 5 GHz WIFI network.