In Colomba, written in 1840, a fiery and romantic tale of revenge among "exotic" peoples meets up with an early example of a mystery story.

At the point Merimee wrote Colomba, the classic mystery story had not yet been "invented" or fully developed as it later would be by writers like Edgar Allen Poe and Arthur Conan Doyle. Nevertheless, Merimee incorporates into his tale some of the elements that would become staple parts of the classic mystery tale. For example, there is objective evidence—and the lack thereof, indicating foul play—in the page torn from the bloody notebook. Colomba insists that her father wrote the name of his murderer on this page and that it was torn out to cover up a crime—not to light a cigar, as is the initial explanation.

With this mystery in play, Merimee incorporates red herrings—misleading clues—to delay the definitive revelation of the murderer. As with a classic mystery, this method of suspense keeps the pages turning.

But the novella is also wrapped up in the romance of the Corisican culture. As he does with the fiery and treacherous gyspy Carmen in his novella Carmen, Merimee creates a tempestuous female character whose "exotic" blood and upbringing leads her to behave in ways more "primitive" than those of the "civilized" Englishwoman Lydia. By 1840, Europe as a whole was industrializing and becoming more homogenized, a trend that had accelerated with the end of the Napoleonic Wars. Significantly, the story is set just after the end of these wars, with old cultures perceived as still intact on Europe's fringes. Merimee's novella reflects the public interest, as these cultures eroded, in the ways of marginalized European peoples who seemed to represent a wilder preindustrial world.

While Italy had long had a hold on the European imagination as a place of mystery and romance, in the nineteenth century, it became more than just a backdrop—as it is, for instance, in Radcliffe's The Mysteries of Udolpho—as the focus shifted to its ordinary native people (not just dukes, princes, and castles) and their ways.

The romantic other would become a feature of the late nineteenth century mystery novel, but by that time, such as in Doyle's Sign of the Four, the "other" would have often (though not always) morphed into the more threatening and sinister figure of the "Oriental."