Since the early 1990s, lifelong learning has become a major policy concern for the European Union, being seen as a means for enabling individuals to be more competitive in social and economic contexts that are continually changing. After a series of white papers and strategies in the field of lifelong learning, the EU launched the Lifelong Learning Programme in 2007, which dealt with the most pressing issues in the field. In light on the complexity of this programme, we need to ask ourselves if traditional evaluation models and approaches are appropriate for evaluating complex educational policies and programmes in the educational field. Thus, the stake of this article is to explore the challenges which arise when evaluating the EU's lifelong learning policies and programmes in general, and the Lifelong Learning Programme 2007-2013 in particular, as well as to propose several new directions for overcoming these challenges.