The style of the game is a composition of survival horror games and tactical RPGs with a grid-based system for combat.
Set in 1898 in Aberystwyth, Wales, the game follows the mysterious occurrences surrounding Nemeton Monastery and the three protagonists who, by chance, are forced to investigate its dark history.
After a series of troubling visions, Koudelka Iasant, a young gypsy girl with supernatural powers, arrives at the Monastery. There she is met by Edward Plunkett, an adventurer, and Father James O'Flaherty, a bishop.
The plot is that a long time ago, an old man was a captain of a ship named 'The Mary Alice' that went down in a terrible accident involving fire. The old man was blamed and received bad treatment before he went into a sad retirement (it is hinted that the fire was actually caused by the cook on the ship). He and his wife, still wealthy from the ship's earnings, purchased an old monastery in Aberystwyth. The old man and his wife (named Ogden and Bessy) became friends with a certain woman named Ellaine. She believed that the boat accident wasn't Ogden's fault. Welcoming of her sympathy and understanding Ellaine and Ogden became very close. Ellaine was married to an alchemist named Patrick. Ellaine had picked Patrick over James (the 3rd character the player finds) as a husband. Patrick had promised James that he would protect Ellaine, but one day, something bad happened. Ellaine was killed by burglars that broke into her house. In their devastation at her death, Ogden and Patrick looked for mystical ways of bringing her back. After much research, Patrick found an ancient text that could bring the dead back to life.
The spell required that several fresh bodies were fed to a cauldron over time. Ogden and Patrick began with prostitutes and thieves but then began to go to nearby towns and abduct innocent people, murdering them horribly at the monastery.
After donating over two hundred bodies to the cauldron, the spell took effect. But, unfortunately, it didn't go as planned. Ellaine's body was resurrected, but not her soul. She was a monster, a beast with the image of an angel. On top of that, all the innocent people who had been sacrificed were awake as well. They came in many forms: ghosts, spirits, monsters, zombies, beasts, etc. What happens in the time between here and the start of the game is unknown. Koudelka is summoned there by the spirit of Ellaine. Edward is there because he heard rumours and came to investigate and James (who is unaware of Ellaine's death at the beginning) was sent there by his coven.
Koudelka is the precursor to Sacnoth's Shadow Hearts series. Shadow Hearts takes place in the Koudelka universe and features various locales and characters from Sacnoth's debut work.
Source: Wikipedia, "Koudelka", available under the CC-BY-SA License.