When Chekhov published this story (1899), Russian Orthodoxy was still dominant and all-pervasive in Russian society. This means that virtually all Russians (seemingly all but not literally all) were deeply religious and held tightly to a religious moral code. Whether they kept the code was a different matter, as Chekhov points out through Anna's story.
The church appears about mid-way in the story, after Anna and Gurov have both succumbed to physical attraction. They left her room together into a "death-like air," then took "a cab and drove to Oreanda." It is here that they took "a seat not far from the church" and "looked down at the sea" while "the clouds stood motionless in the mountain-tops" around them.
"I found out your surname in the hall just now: it was written on the board -- Von Diderits," said Gurov. "Is your husband a German?"
"No; I believe his grandfather was a German, but he is an Orthodox Russian himself."
At Oreanda they sat on a seat not far from the church, looked down at the sea, ... white clouds stood motionless on the mountain-tops. ... the monotonous hollow sound of the sea rising up from below, spoke of ... the eternal sleep awaiting us [death].
The church is a pivotal symbol in Chekhov's psychological exploration of living, motive, death and punishment. The church enters the setting after three important story elements: (1) Anna says she feels wicked and in need of forgiveness; (2) Gurov grows excessively bored with hearing her laments; (3) Anna says her husband is a convert to Russian Orthodoxy. Every Russian reading Chekhov's story in the nineteenth century would have known precisely and exactly what Chekhov's point was in including the Orthodox church. More than a hundred years later, we have a little more trouble with it.
The juxtaposition of the Gurov's and Anna's immorality, her realizations and need for forgiveness, and her husband's Orthodoxy represents Chekhov's commentary on the ineffectiveness of religious training (Gurov doesn't care and Anna can't obey); the state of morality in the 1890s in Russia; and the seeming irrelevance of the all-pervading presence of Orthodoxy.
Chekhov is suggesting that the Orthodox religion has little effect on actual living even though it dominates life's structure. He seems to be suggesting that Orthodoxy is not what motivates actions, though it motivates guilt feelings after actions are taken. He is definitely pointing out the ultimate death ("the eternal sleep awaiting us") that lies before each of us and seems to be suggesting that eternal punishment may not lie before us alongside death.