How do you enable Google Location History on an iPhone?
I found the answer myself. For some reason, enabling the device through the Google app did not work, however the same screen in Google Maps works fine. 

Open the Google Maps app > Menu > Settings > Location history > Enable the device.