The California-based social networking site has long required users to register with their real names - a policy that the data protection commissioner of Schleswig-Holstein state says is in breach of German law and European rules designed to protect free speech online.
The commissioner, Thilo Weichert, ordered Facebook on Monday to rescind its real name policy immediately.
"We believe the orders are without merit, a waste of German taxpayers' money and we will fight it vigorously," Facebook said in a statement. The company claims that its real name policy is intended to protect users.
Weichert told The Associated Press that Facebook has two weeks to respond. If it fails to comply with the order, his office can impose a penalty against the company, said Weichert.
The maximum fine would be only €50,000 ($66,000) - peanuts for a multinational company, but nevertheless a symbolic blow that could also lead to a tougher stance from other German and European privacy regulators.
"We have the right to prevent this data protection breach," he said. "Theoretically we can order the website blocked, but that would be disproportionate."
German privacy rules have posed a legal headache for Facebook, Google and other web giants in recent years. The country has strict laws on data protection that give consumers significant rights to limit the way companies use their information.
Weichert has previously warned investors against buying Facebook shares, warning that the company's "business model will implode" because Facebook users' private information is used in breach of European law.
Facebook says it has more than 20 million active users in Germany.