The $17m will be divided between 37 US states and Washington DC, who brought claims against the search giant after it emerged that it was secretly tracking millions of Safari users.
Google is alleged to have tweaked its DoubleClick cookie code to circumvent the Apple browser's default privacy settings, which automatically blocks third party cookies.
Google confessed to the activity in February 2012, but denied any wrongdoing - it claims the code tweak was intended to make ad recommendations easier, with unexpected side effects. In reality, the data collected by Doubleclick cookies could be used to identify individual Safari users and monitor their movements. Google reassured users on Monday that the cookies "collected no personal information".
Announcing the settlement, New York attorney general Eric Schneiderman commented:
"Consumers should be able to know whether there are other eyes surfing the web with them. By tracking millions of people without their knowledge, Google violated not only their privacy, but also their trust."
Under the terms of the settlement, Google will be removing any remaining cookies and will not use this kind of code again. Moreover, Google has committed to educating users about cookies for the next five years; a page or pages on the Google.com domain must be launched to "inform an ordinary user" about cookies and how to manage them.
The $17m settlement follows the record $22.5m fine Google paid to the FTC in August 2012 for the cookie controversy. However, the combined $39.5m will not severely affect the company which made $50bn (£31bn) last year - equating to $136m per day.
Natalie Booth, head of search at theEword, commented: "Privacy is obviously a huge concern to internet users, and secret cookie usage like this can't be taken lightly by governments. However, Google has obviously made great strides recently to protect its users, especially in the wake of the NSA scandal - this settlement may be another step to repairing its reputation."