This answer only concerns England. I don't have the necessary expertise to comment on the rest of Europe, but it may have been similar.

During the pre-Christian Anglo-Saxon period, society attached no discernible value to virginity. Additionally, re-marriage was not only not taboo but encouraged (as unmarried women had little social value). There are even cases of new kings marrying their step-mothers.

This changed when the Anglo-Saxons began to adopt Christianity. The concept of virginity first became relevant to them in a monastic context. The first English monasteries were strongly tied to royal families. Margaret Ross (Concubinage in Anglo-Saxon England) writes that royalty "treated the abbatial office as an extension of family property". It became typical to send otherwise "valueless" women to become nuns or abbesses. Occasionally the title would even pass from mother to daughter. This presented a theological problem, because theoretically nuns ought to be virgins, while in reality they were often widows or otherwise sexually active. Remarriage also became frowned upon.

Fortunately for them there was a solution to this apparent contradiction. The monk Aldhelm wrote a treatise on virginity entitled "De Laude Virginitatis". It argued that rather than the binary definition of virginity prevalent among much of Christendom (and indeed in modern Western society), there were two orders of virginity. The first order of virginity was the one we are familiar with today. A "perfect" virgin has never had intercourse at all. In Anglo-Saxon religious writing such virgins were sometimes associated with miraculous occurrences, for example their bodies would not decay when they died (there are a few examples of this in Bede). The second grade of virginity was defined as "the strict moderation of chastity". And this to the Anglo-Saxons was all that was required of a monk or nun. To the Church outside of England, both the concept of "family monasteries" and the very liberal definition of virginity was seen as "a shocking breach of monastic principles" (Campbell, The Anglo-Saxons), but accepted it as without such breaches it is unlikely that monasticism would have been adopted at all.

Over time, Christianity became more entrenched and the notion of virginity became relevant outside of monastic settings. The Church in England gradually became closer in doctrine to Rome, though even monastic orthodoxy was only "completely" brought into line after the Norman Conquest. This naturally created the popular notion of virginity, as local preachers entrenched Christian values into English society.

As an aside, the introduction of the concept of virginity closely mirrored the introduction of the concept of the innocence of childhood. Nick Stoodly (From Cradle to Grave) writes that "the early Anglo-Saxons did not differentiate between children and adults, that younger individuals were exactly that." The rise of monasticism introduced the notion of innocence initially through the adoption of child-monks (oblates), and as Christianity became entrenched in popular society the concept spread and became more generalized. Christianity held that children were less tainted by worldy sin, and as such made excellent monks (St Columban was vocal on this topic). The Anglo-Saxons previously had no notion of original sin or childhood innocence. The two concepts (virginity and childhood) are very much related when we're talking about the history of sexuality.