Although refered to in 16th century literature, examinations of records by historians have found no evidence of its existence in mediæval times. (Source: 1911 Encyclopedia Britannica) In some feudal systems the culagium was imposed by the local lord: a requirement that a peasant get permission to marry from his lord, which often involved a fee. Ecclesiastical authorities in some regions also demanded a fee before a new husband was allowed to consummate his marriage with his wife. The right of the first night, however, is unlikely to have existed and is probably a distortion based on these.
In the 16th century Boece refered to the decree of the invented Scottish king Evenus III that "the lord of the ground sal have the maidinhead of all virginis dwelling on the same." Legend has it that Saint Margaret procured the replacement of jus primae noctis with a bridal tax. King Evenus III did not exist, and Boece included a lot of other material in his account that was clearly mythical.
Boece was not alone in his mention of the law: Voltaire refered to it in 1762, it was used in Beaumarchais' The Marriage of Figaro, as a plot device in the movie Braveheart by Mel Gibson and is jokingly refered to in Nineteen Eighty-Four in Chapter 7 of the first part.