Install and set up Trusted Contacts
This is a hot question and a top Google search result, but the the other answers here are a little outdated. There is a workaround to get location history working, and all it takes is to install and set up Google's "Trusted Contacts" app (you can uninstall it right after).
Despite Google's message: "use a location enabled Google app on the iOS device to change the setting", I have found no logical way to enable Location History in any other Google app.
Yes. It is absolutely ludicrous that this is what you have to do to enable Search History on an iPhone (you would think that Google would make it easier to voluntarily give them your data). But I'm not putting Google down. They make a lot of amazing products. This must just be a small glitch that they'll fix in the future.
Luckily it can be fixed in 2 easy steps:
1. Make sure "Location Services" is on
Make sure you have Google Maps installed, next: as per Google Maps Support, make sure that Location Services is on.
Go to the Settings app.
Make sure the
Location Services toggle is on.
Then, still in
Location Services, look for
Google Maps and make sure "Always" is selected.
2. Install and set up Trusted Contacts
Install Trusted Contacts from Google LLC in the App Store.
Open the app and follow all the setup instructions.
When you get to the "Share your location?" screen, tap "TURN ON". This is the most important step.
Finish setting up the app.
Now Location History will be enabled on your iPhone! Verify by going to Location History in your Google Account settings, opening the "Devices on this account" drop-down list and making sure your iPhone has a check next to it.
Optionally, you can now uninstall Trusted Contacts.
Important: turning off location services or going into low-power mode will most likely (now and in the foreseeable future) stop Google from saving your location history. Keep location services on and do not go into low-power mode if you want your location history to be saved.