It all depends on the meaning of the term and on the period, considering the differences between annulment and modern divorce.
Marriage became a sacrament only in 1215 with the Fourth Council of the Lateran, after a period when there were no marriage contracts and marriage could be dismantled (according to the French Wikipedia article on history of divorce). The church opposed this practice but had difficulty in imposing its views even after 1215, as the answer on the Spanish cases shows. Annulment and divortium in the sense of "Séparation de corps" were practiced as an alternative to the divorce in the modern sense, as they preserved the sanctity of marriage.
Remariage seems more problematic, notwithstanding the Spanish cases. But practically one can imagine that it was not impossible, the farther one went from the location of the previous marriage, given that centralized records were absent.
In a larger sense, divorce seems much older in European countries than the dates posted in answers here in relation with England and Prussia, which invoke modern legislation.
More or less amusing, one reason for the mariage to be annulled was sexual impotence, which (at least in France) needed to be proved or disproved within the ancient judicial institution of Congrès.
Quick translation from French Wikipedia:
In the Middle Ages, until the beginning of the eighteenth century, the
Congress was a judicial ordeal, ordered by the judicial authority generally at the demand of the wife, which the husband had to undergo in
order to prove his sexual potence in view of the cancellation of
mariage or of divorce. In the presence of judges, officials,
councilors, lawyers, court clerks, and medical experts, the spouses
were united in a closed bed that was in use at the time, and it was
for the Court to witness the impossibility of sexual relation between
the spouses. This process, which was somewhat of an ordeal, was
gradually abandoned as unreliable, as some husbands who had been
impressed by the solemnity of the judicial system, proved fertile
after remarriage.
The Wikipedia page lacks references and may be incorrect (mentions both divorce and remarriage instead of just annulment, and a later date for the end of the practice), but some references can be found here.
The article is from the Grand Dictionnaire Universel of Pierre Larousse, of 19th century.
The practice seems to have been abolished in 1677.
