The law would also allow investigators to obtain personal data from companies such as banks and airlines, the state Justice Ministry announced yesterday.
With the new legislation, the NRW state government is responding to the numerous local arrests of foreign students and business people linked to the 11 September attacks in the US.
NRW state justice minister Fritz Behrens said police needed extended surveillance powers to delve deeper into the structures of international terrorism.
In addition to the new law, the government plans to increase the number of investigators fighting terrorism and equip them with new technology, Behrens said. He declined to provide details.
The NRW initiative goes one step beyond the so-called Security Package II, a special bundle of surveillance laws approved by the federal government at the end of last year.
These laws created a new level of government surveillance, making it much easier for federal and state law enforcement and special crime forces to tap telephone calls, screen e-mail and obtain personal data from public administration agencies and private companies.
A spokeswoman said the state government aims to approve the new law by August.