Passing the legislation late Thursday evening as part of a marathon session, the lower house the Bundestag made gun owners subject to random checks not requiring any specific suspicion of wrongdoing.
They will also face heavier penalties should it be found they are not keeping their firearms according to regulations. Those owning guns illegally have until the end of the year to surrender them without consequence under a limited amnesty.
The new law also aims to have a national firearm registry by 2012.
The changes were sparked by the Winnenden school massacre in March, when 17-year-old Tim Kretschmar murdered 15 people with a gun taken from his father's bedroom.
The tighter gun controls are widely supported in Germany and the opposition criticized the new law for not going far enough.