Fundamentally, researching the history of a day when everyone lies to you is pretty hard. In fact, I might be lying to you in this post, but I'm not, although my sources might be. Joy.

Ok, so according to Wikipedia, [Not a great start, but what the hey.] The first reference to foolishness and April 1st was in Geoffrey Chaucer's The Canterbury Tales 1392. I tracked what was actually said down on english.fsu.edu in the The Nun's Priest's Tale we find something like this.

(The month of March, when God created man) Was over and indeed had been exceeded (The days were thirty-two that were completed),

It does not take a mathematical genius to figure out that the date she is referencing is April 1. 32 days after March starts is April 1. And indeed, in the story the rooster acts foolishly. I think that this is actually a pretty strong reference.

However, there are some strong counterarguments. In pretty much all of the Canterbury Tales has someone who acts foolishly. Furthermore, there is a possibility that this refers to the anniversary of the engagement of Anne of Bohemia and King Richard II on May 2, which is 32 days after the end of March. This seems somewhat unlikely to me, as by the time that Chaucer probably started to work on the Cantabury Tales around 1386, Anne and Richard had already been married for four years. If Chaucer wanted to indirectly reference them through a date, I would think that the date of the marriage would seem more likely. Additionally, April fools is mostly known for lies and pranking, however that is not how any of the characters act.

The next good reference is over a hundred years later in 1508 by Eloy d’Amerval. In his massive poem " Le livre de la deablerie" he mentions 'poisson d'avril' which means April Fish, or as we would say April Fool. From what I've been able to gather here is how it reads in the original.

Viença, le chief des ruffyens, Houlier, putier, macquereau infame De maint homme et de mainte fame, Poisson d'apvril, vien tost a moy

I can't read french, and so I've had to rely on what others have said about the translation. In essence it reads like "Vienca, the chief of ruffians, infamous procurer of many men and women, april fools, come here now" I'm 99% that is a horrible translation. However, idiomatically, I think the last bit might be translated as similar to "Come here you idiot."

In any case, Poisson d'apvril is the french word for April Fools and from what I've gathered this is the first appearance of that phrase.

In 1561 Eduard de Dene wrote about a Lord who sends his servants on foolish errands on April first. I was able to find the original text on hoxes.org. However, I can't read dutch either. The title is "Refereyn vp verzendekens dach Twelck den eersten April te zyne plach" Which is translated to Refrain on errand-day which is the first of April. Then repeated at the end of each paragraph is the phrase "Ick vreese tian dat ghy my wilt verzenden." This apparently translates to "I am afraid... that you are trying to make me run a fool’s errand."

de Dene's reference is extremely strong. More importantly, it appears to have someone doing a foolish errand for someone else. This is interesting because Irish tradition you send someone with the message "send the fool further."

The most commonly cited major change that resulted in April fools is the calendar change in 1582. This resulted in the year starting on January 1st rather then March 25th. However, the change was slow to take hold due to the conflict between Catholics and Protestants. Indeed, the British did not adopt the new calendar until 1752.

In 1686, John Aubrey wrote that "Fooles holy day. We observe it on ye first of April. And so it is kept in Germany everywhere." and in 1689 there was a prank where some people were sent to watch a fictitious 'Washing of the Lions." However, it is certain that by the late 1700's the tradition of April fools was well established almost everywhere. ^Cite

It is my opinion that the conflict between the old style of dating and the new style probably brought a relatively minor tradition of sending someone on a fool's Errand on April 1st into larger prominence. Someone was a fool for thinking the year started on March 25th, so you sent him on a fools errand like one.

I also used the Encyclopedia of Deception entry on April Fools in researching this. I hope it is an enjoyable read, I enjoyed researching it, and that it meets the standards of this subreddit.

Follow up question: Was there ever an April Fools prank/joke someone pulled that got them charged or executed?