Andrey Threat:
Since others, including myself, have experienced no issue with com.apple.Safari.History, the problem cannot be the software, itself, but must be something else that the software interacts with.
Safari’s syncing over iCloud may or may not use that process. I’m not certain either way.
When you wrote «As soon as I turn it on», what was the “it” to which you were referring? Safari? «safari iCloud sync», whether Safari is running or not?
If the latter, then it may not be your local Safari History, but something about what is being synced over iCloud. This could involve your other Safari versions, or something else.
Do you have anything besides other versions of Safari that are being synced with Safari?
(It seems like even older versions of macOS have received Safari updates, relatively recently, though I’m not sure how universal that was.)
It’s certainly up to you whether you clear your Safari History, or not.