"I am a Roman Catholic," he told the rabbi, who with his long beard, and black coat and hat was clearly identifiable as an Orthodox Jew. "I just wanted to tell you how important the Jewish religion is to me."
Such are the contradictions of being a Jew in Austria today, where philo-Semitism can be used as a personal and political tool to balance fears of rising right-wing extremism and the lingering legacy of Austria's Nazi past.
Earlier that day, a stony-faced President Thomas Klestil had sworn in Austria's controversial new right-wing government, despite diplomatic sanctions by the European Union, Israel and the United States.
Noisy demonstrators marched through the city for hours, protesting the entry into the governing coalition of the far-right, xenophobic Freedom Party and carrying placards that compared party leader Joerg Haider with Hitler.
There were violent clashes, and riot police used water cannons against youthful protesters.
The rise of Haider and his Freedom Party have triggered deep concern among Austria's 10,000 Jews, not just as Jews per se, but within the broader context of concern for their country as a whole.
"Democracy and the mentality of civil society are underdeveloped here," said a Viennese Jewish writer just hours after the new government was sworn in.
Said businessman Robert Liska, a member of the local Jewish community board, "I don't think of it as a Jewish question at all. Jews are affected as much as are Protestants and Catholics. No one knows how it really will be. Jews and other minorities will be warned and will watch the situation."
Before the Freedom Party joined the governing coalition, the president of Austria's Jewish community, Ariel Muzikant, had been vociferous in his condemnation of Haider to the point where Haider had threatened to sue him.
As of this week, however, the Jewish community has not taken a formal stand or issued a formal reaction to the new government.
"Officially, the community is numb," said a community leadership insider. "They are making no comments. There is a sort of silent evaluation process going on."
Austria had some 185,000 Jews in 1938 when Hitler annexed the country -- with the enthusiastic support of most Austrians. Many leading Nazis, including Hitler himself, were Austrian-born.
Nearly 70,000 Austrian Jews were killed in Nazi death camps, and 70,000 more were driven out of the country.
After the war, however, the Allies referred to Austria as Hitler's first victim.
There was no real confrontation or public recognition of its role in the Shoah until the late 1980s, when Austria elected Kurt Waldheim as president, despite revelations that he hid a Nazi past.
Today, most of Austria's Jews live in Vienna, and most are Holocaust survivors, displaced persons or refugees from Eastern Europe and the Middle East and their descendants.
They run the full range, from prosperous businesspeople to intellectuals, from fervently Orthodox to Reform, from Austrian-born to recent immigrants from the former Soviet Union.
Haider's party came in second in last October's elections, capturing just more than 27 percent of the vote. It was the best showing by a far-right party in Europe since the end of World War II.
Most members of the Jewish community are believed to have voted for the Social Democratic Party, the Greens or the tiny Liberal Party.
Only one Jew is publicly known for supporting Haider's Freedom Party -- journalist Peter Sichrovsky.
"Haider wanted Sichrovsky to be a bridge with the Jewish community and to soften its image abroad," said a Jewish art historian. "But it backfired. He is totally ostracized by the community."
During the campaign, Haider's platform was not openly anti-Semitic, but his strident xenophobia raised fears that anti-Semitism could become a by-product of his rhetoric, particularly as an undercurrent of anti-Semitism still persists among some sections of the Austrian public.
"I get it on the street," said a young Chabad rabbi who preferred not to give his name. "People will laugh and point. The atmosphere was cold, is cold and will be cold. It will never change unless the people change."
Anti-Semitism "can be easily aroused by discussion over art restitution, general restitution, money claims, and the like," said Marta Halpert, director of the Anti-Defamation League's office in Vienna.
"You have two possibilities -- to stay here and be active or run away," said Jewish researcher Peter Bettelheim. "I am going to try to organize a group of friends into a political human rights movement with a clear strategy."
Jews of all ages take part in the daily demonstrations held to protest Haider .
White-haired Mira Atlas said she takes to the streets.
"I don't trust Haider at all, even though he has made statements now pledging democratic policy," she said, as she made sandwiches for the weekly club she leads for Jews who have immigrated to Austria over the years from Russia.
"He is a very powerful speaker, he really speaks well," she said. "So did Hitler."