The law, which passed with 398 legislators voting in favor and 170 against and five abstentions, was the result of several years debate over how to better integrate the estimated 15 million people living in Germany who have a foreign background.
Under the agreement, 100,000 migrants whose asylum applications were turned down, but were allowed to remain in the country, will be issued with a work permit. If they find a steady job by the end of 2009, they will be granted the right to stay on indefinitely.
"This law will allow for better integration," Interior Minister Wolfgang Schaeuble said following the vote.
Other key points of the bill include raising the legal age that a spouse can enter the country from 18 to 21, in an effort to clamp down on forced marriages; requiring proof of basic German language skills for newcomers; and a requirement that some foreigners entering the country submit a digital photograph and fingerprints.