The firm previously held information about searches for an indefinite period but will now anonymise it after 18 to 24 months.
"This is an extremely positive development," said Ari Schwartz, deputy director of the Center for Democracy and Technology, a US-based watchdog.
"It's the type of thing we have been advocating for a number of years."
However, governments could still force Google to hold onto data or hand it over to authorities.
"By anonymising our server logs after 18 to 24 months, we think we're striking the right balance between two goals: continuing to improve Google's services for you, while providing more transparency and certainty about our retention practices," a statement from the search giant said.
It's a step forward, but I would like to see them anonymising data in a much shorter period
Richard Clayton, Cambridge University
It added: "Unless we're legally required to retain log data for longer, we will anonymise our server logs after a limited period of time."
Peter Fleischer, Google's privacy counsel for Europe, said the decision has been taken after consulting with privacy bodies in the US and Europe.
He said: "We believe that privacy is one of the cornerstones of trust. We will be retroactively going back into our log database and anonymising all the information there."
Rolled out
Mr Fleischer said the firm was holding on to the information for up to 24 months in part to match data retention laws being rolled out across Europe.
European internet service providers (ISPs) and phone companies are in the process of implementing an EU directive which forces them to retain a variety of communication data for up to two years.
Google collects and stores data from each query. It holds information such as the search term itself, the unique address of the PC being used, known as the IP address, and details of how a user makes searches, such as the browser used and previous queries to Google.
That information can contain private data about a user, and could be used to build a detailed picture of the user's habits or lifestyle.
Google says it was using this information to help improve its different services and to monitor how its search engine was functioning.
Online habits
Privacy groups are concerned about how the data collected by Google - and other web firms - could be used to monitor people's online habits.
Richard Clayton, a researcher at Cambridge University specialising in web traceability, said Google's announcement was positive but had not gone far enough.
"It's a step forward but I would like to see them anonymising data in a much shorter period.
"There is no justification for holding on to the data for two years."
Mr Clayton said the data Google collected was useful to the firm in improving its services only in the short term.
He said that Google was hiding behind the European directive in setting time limits on how long it should hold on to the data.
"There is no sense of whether this directive even applies to web search logs," he said.
He said the real reason Google was holding on to the data was because of the cost involved in anonymising it.
He said he also had concerns about how the firm was ensuring that held data could not be traced back to individual users.
Google has said it will alter the data so that users' searches cannot be traced back to an individual's computer.
But Mr Clayton said the recent row over search data released by AOL showed that identification of users could still be made even without a machine's unique IP address.
AOL released data to academics last year relating to millions of search queries carried out by its users. While there was no direct identifying data, there was enough information in the searches to build profiles of users.
It is not yet clear if other search engines will follow suit. No-one at Yahoo or MSN was available for comment at the time of writing.