The Associated Press reported that many Google services on Android devices and iPhones store your location data, even if you have used a privacy setting which states it will prevent Google from doing so.
Computer science researchers at Princeton University in the US confirmed the report's findings.
For the most part, Google is up-front about asking permission to use your location information.
An app like Google Maps will remind you to allow access to location if you use it for navigating. If you agree to let it record your location over time, Google Maps will display that history for you in a "timeline" that maps out your daily movements.
Storing your minute-by-minute travels carries privacy risks and has been used by police to determine the location of suspects. However, the company will let you "pause" a setting called Location History.
Google said this will prevent the company from remembering where you have been.
The tech giant's support page on the subject states: "You can turn off Location History at any time. With Location History off, the places you go are no longer stored."
This is not true, the AP report found. Even with Location History paused, some Google apps automatically store time-stamped location data without asking.
For example, Google stores a snapshot of where you are when you simply open its Maps app. Automatic daily weather updates on Android phones pinpoint roughly where you are. And some searches that have nothing to do with location, such as "chocolate chip cookies", or "kids science kits" pinpoint your precise latitude and longitude - accurate to the square foot - and save it to your Google account.
The privacy issue affects some two billion users of devices that run Google's Android operating software and hundreds of millions of worldwide iPhone users who rely on Google for maps or searches.
Storing location data in violation of a user's preferences is wrong, said Jonathan Mayer, a Princeton computer scientist and former chief technologist for the US Federal Communications Commission's enforcement bureau.
A researcher from Mr Mayer's lab confirmed AP's findings on multiple Android devices. AP also conducted its own tests on several iPhones that found the same behaviour.
Mr Mayer said: "If you're going to allow users to turn off something called 'Location History', then all the places where you maintain location history should be turned off.
"That seems like a pretty straightforward position to have."
Google insisted it has been perfectly clear.
The company said: "There are a number of different ways that Google may use location to improve people's experience, including: Location History, Web and App Activity, and through device-level Location Services.
"We provide clear descriptions of these tools, and robust controls so people can turn them on or off, and delete their histories at any time."
To stop Google from saving these location markers, the company says, users can turn off another setting, one that does not specifically reference location information. This setting, called "Web and App Activity" and enabled by default, stores a variety of information from Google apps and websites to your Google account.
When paused, it will prevent activity on any device from being saved to your account. But leaving "Web & App Activity" on and turning "Location History" off only prevents Google from adding your movements to the "timeline" - its visualisation of your daily travels. It does not stop Google's collection of other location markers.
You can delete these location markers by hand, but it is a painstaking process since you have to select them individually, unless you want to delete all of your stored activity.
You can see the stored location markers on a page in your Google account at myactivity.google.com, although these are typically scattered under several different headers, many of which are unrelated to location.
To demonstrate how powerful these other markers can be, AP created a visual map of the movements of Princeton post-doctoral researcher Gunes Acar, who carried an Android phone with Location history switched off, and shared a record of his Google account.
The map includes Mr Acar's train commute on two trips to New York and visits to The High Line park, Chelsea Market, Hell's Kitchen, Central Park and Harlem. To protect his privacy, AP did not plot the most telling and frequent marker - his home address.
Huge tech companies are under increasing scrutiny over their data practices, following a series of privacy scandals at Facebook and new data-privacy rules recently adopted by the European Union.
Last year, the business news site Quartz found that Google was tracking Android users by collecting the addresses of nearby mobile phone towers, even if all location services were turned off. Google changed the practice and insisted it had never recorded the data anyway.
Critics say Google's insistence on tracking its users' locations stems from its drive to boost advertising revenue.
Peter Lenz, the senior geospatial analyst at Dstillery, a rival advertising technology company, said: "They build advertising information out of data. More data for them presumably means more profit."
Since 2014, Google has let advertisers track the effectiveness of online ads when it comes to driving foot traffic, a feature that Google has said relies on user location histories.
The company is pushing further into such location-aware tracking to drive ad revenue, which rose 20% last year to 95.4 billion dollars (£74.6 billion).