In the Ultimatum Game, two players are offered a chance to win a certain sum of money. All they must do is divide it. The proposer suggests how to split the sum. The responder can accept or reject the deal. If the deal is rejected, neither player gets anything. The rational solution, suggested by game theory, is for the proposer to offer the smallest possible share and for the responder to accept it. If humans play the game, however, the most frequent outcome is a fair share. In this paper, we develop an evolutionary approach to the Ultimatum Game. We show that fairness will evolve if the proposer can obtain some information on what deals the responder has accepted in the past. Hence, the evolution of fairness, similarly to the evolution of cooperation, is linked to reputation.