Politkovskaya, 48, known for her criticism of the Kremlin's policy in Chechnya, was gunned down in an apparent contract killing in a lift in her apartment bloc in Moscow October 7.
"On November 24, two employees at Novaya Gazeta were threatened with murder," the newspaper said on its Web site.
Following their colleague's killing, the journalists started an independent investigation.
"The first threat was linked to an article on problems in the North Caucasus, and the second to investigations into the murder of Anna Politkovskaya," the newspaper said.
The editor-in-chief, Dmitry Muratov, said the newspaper had received an e-mail Friday and a text message. "The first contained a proposal to the leading columnist, and the other was addressed to the head of the main editorial department."
One of the newspaper staff also received a text message with a death threat and his home address, Novaya Gazeta said.
Muratov declined to give further details, citing an agreement with police.
"We immediately informed law-enforcement agencies, because we could not quite understand what was happening," he said, adding an investigation was already underway.
Law-enforcement officers could not be reached for comment.
Add to blog
You may place this material on your blog by copying the link.
Image Galleries: Siberian Air Base Gets New Su-30SM Fighter Jets
Infographics: First Russian Smartphone
New ties between Russia and Japan would mark not only a breakthrough in their relations but also a significant shift in Northeast Asia’s political dynamic. Both are secondary players in a region overshadowed by an increasingly assertive China, which has not hesitated to push against the boundaries of its neighbors.