As always, it depends on where and when you are. Starting in the 12th century and much more definitely in the 13th century, and especially in urban areas, you’d simply go to a notary like you would today and have a document written up.

Before that, the concept of legal written documents did exist, but something like a will probably wouldn’t be written down, it would most likely be an oral contract. You would simply tell your family and friends what you wanted, and hopefully they’d do it. They could also swear solemn oaths on religious books or relics of saints, to add weight and certainty. If there was still a dispute about what was supposed to happen, the church or a local secular authority could conduct an investigation and hopefully figure out who swore to do what.

Couldn’t they lie about it though? Sure they could, but they probably wouldn’t, because their culture depended on memories being passed down over generations and on people keeping the oaths the they swore. In fact they sometimes were suspicious of written legal documents. If most people were illiterate and only a special class of scribes wrote things down, why should they necessarily trust a written document?

But gradually in the 11th and 12th centuries, written law became predominant. This was when universities began to be founded, and (especially in Italy and southern France) Roman law was “rediscovered” - well, it never really went away, but it began to be studied in greater detail, especially at the new University of Bologna. Students who were trained in Roman law, the canon law of the church, the Latin language, and classical Latin literature became a class of professional scribes and writers. Those who studied Roman law found it was great for a lot of different things, but especially for contract law - and now they had the vocabulary and the skills to apply Roman contract law to medieval situations.

At first, professional legal scholars were all priests or other members of the church (“cleric” and “clerk” come from the same Latin word). Clerks offered their services to royal (or other aristocratic) households first, which helped ensure that Roman legal principles took hold in the secular world as well the ecclesiastical world of the church and the university. But there were a lot of clerics, and they realized they could work for other secular, non-royal institutions as well - city governments, merchant communes, really anyone who needed a fancy legal framework to conduct their business.

But a clerk isn’t a notary - a “notarius” was literally a secretary or someone who took notes. So how did notaries take on the functions of a clerk? Well there isn’t really a single answer for that because (and here’s the wishy-washy explanation everyone loves for medieval questions!) notaries evolved differently depending on the time and place. They could be university-educated but they could have learned on-the-job as apprentices. They could be accredited by a town government, by the church, or by a royal court.

Medieval authors recognized that notaries were a separate thing and there was an “ars notaria”, a “notarial art” that differed from other kind of writing. There were notarial manuals explaining how to write the types of documents that notaries typically wrote. But the kinds of documents they were allowed to produce also differed from place to place, depending on local laws and customs. Criminal cases were always handled by a government court (royal or otherwise). Disputes over property worth more than a certain amount of money probably couldn’t be solved by a notary either. Minor property disputes, minor debts, business contracts, and wills were usually within the jurisdiction of notaries. It would have been too difficult for everyone to have their contracts and wills approved by one court. It would take too long to get a hearing in the court, and why should the monarch or the church or the local government care about a contract between two merchants, or someone’s will?

No one ever specifically delegated these matters to notaries, it just seems to have kind of happened on its own. People went to notaries because it was too time-consuming, or too expensive, or too much of a burden to go to the local court. Then since notaries were already handling these matters, everyone recognized that this was a good idea after all!

So, to give you a specific example, I’ll have to stick with the region I know best - the crusader states in the eastern Mediterranean. As always for the crusader states, it’s also good to keep in mind that they’re a bit unusual compared to urban centres back in Europe. But still, this is probably fairly representative of how notaries worked.

In 1264, a wealthy merchant in Acre named Saliba was sick and wrote his will. Acre was the capital of the Kingdom of Jerusalem at the time (the crusaders no longer controlled Jerusalem), and the headquarters of the Latin church and the military orders, including the Hospitallers, with whom Saliba was very close. Saliba wasn’t a Latin Catholic like the European crusaders, but he was some kind of eastern Orthodox Christian (probably Syriac). His will begins:

“…I, Saliba, a burgess of Acre, confrater of the Hospital of St. John of Jerusalem, weak in body though healthy in mind, and good and sound in memory, make and ordain in the following way my announced testament, or my last will, concerning my goods and property.”

Sounds almost modern - you still have to be “of sound mind” to leave a will today. He appointed some of his Hospitaller friends as executors to make sure that all the money he bequeathed went to the right people and places - various churches in Acre, his children, his sister and her children, even his slaves (he owned several enslaved Muslims), as well as some money that was apparently intended as a kind of charity for the “workers of Acre” in general. Most importantly for us here, at the end there is this note:

“I, Gerard Bonisani, judge and public notary established in Acre by the authority of the holy Roman church and of the commune of Marseilles, was involved in all the aforementioned matters, and I wrote this at the command of the aforementioned witness, and I issued the document in this public format.”

In Acre and other cities in the Kingdom of Jerusalem there were merchant neighbourhoods from several Mediterranean city-states (Pisa, Genoa, Venice, Marseilles, etc) and they all had their own notaries. They probably originated with scribes who travelled to the east on board merchant ships, and who wrote contracts for business partnerships that were made during the voyage. They stayed in the crusader cities in the east during the sailing season and went home for the winter. Eventually when the merchants were given their own neighbourhoods, the notaries could stay there permanently. Just like in Europe, merchants and anyone else who needed a document could visit one of these notaries rather than having to wait for the royal court. Here, Saliba hired a notary from Marseille, which was actually the smallest foreign community - most notaries were from the Italian cities. Gerard noted that he was registered back home in Marseille, and with the church; since Marseille was theoretically part of the Holy Roman Empire, maybe he was registered with the empire as well.

You didn’t need a notary to make a will of course - there are plenty of examples of royalty or other aristocrats making wills the old way, through royal or ecclesiastical charters. For example, Louis VIII of France left all of southern France to his son Alphonse of Poitiers, after conquering it from the Count of Toulouse. Alphonse married the heiress of Toulouse, Joanna, who also left a will when she died in 1271 - but her will was invalidated by the royal court because it would have made some of that territory independent of the French crown again. (However she did successfully bequeath the city of Avignon to the Pope, who ruled it all the way up to the revolution in the 18th century).

Notaries were trained to write in Latin (even if sometimes it wasn’t very good Latin), but with royal charters sometimes you see wills in a vernacular language. The 1281 will of the relatively minor noble Gui de Lusignan, lord of Cognac (and a younger son of Hugh X of Lusignan, Count of La Marche and Angouleme) was written in French. It was witnessed and signed by other noble members of his family and presumably written by a clerk, but no notaries are mentioned.