To complete the headline, only when iCloud is enabled. Anyone especially concerned about privacy shouldn't be using iCloud anyway, but it definitely needs more fine-grained control.
I kinda assumed that after I had my call history on my Mac and iPad Facetime apps, since it is possible to call using any iOS/macOS device in the network.
You don't always have the phone reachable, so I assumed it syncs over iCloud.