Pieter Brueghel, Carnival on the left and Lent on the right
In the later Roman Empire, around 300 AD, people began fasting for Lent, for the forty days before Easter. On the first day of Lent, people went to special church services and smeared ash on their foreheads to show they were mourning - grieving. Lent always begins on a Wednesday, so people began to call the first day of Lent "Ash Wednesday."
There was a big Roman festival that happened in the middle of February, the Lupercalia. Of course if you became a Christian you couldn't celebrate the Lupercalia anymore, but people missed it. "Stop celebrating Lupercalia!" people whined. "But we like Lupercalia! It comes in mid-winter when we are all cold and cranky and bored and it cheers us up!"
Then it occurred to people that it still might be cool to have a big party the night before Lent started, to eat all the things you wouldn't be eating during Lent, like meat and beer. The night before Ash Wednesday is always a Tuesday, so people called this party "Fat Tuesday". You were eating fatty things and getting fat. In French Fat Tuesday is "Mardi Gras", which is what we usually call this party today. Or people call it "Carnival", which comes from the Latin "carnem levare" - carry away the meat.