Pretty sure Location History was never on by default for my Google account, I had to explicitly turn it on.

In fact on every new device I seem to have to enable it separately.