ICloud – Stop syncing Safari History through iCloud between 1 or more computers or iOS devices

Unfortunately you have to turn it on and then it will let you change it. I'll have a look tomorrow to see if there is a preference file that can easily be changed to skip having to sync with IE.

Sign out and sign back into iCloud on your Mac.

There was also a bug that if you had iCloud drive turned off for safari, your tabs wouldn't sync. So I would make sure that Safari is checked under iCloud Drive as well as iCloud settings.