There are at least two reasons why labels are better than legends. First, when the labels are on the chart, users don't have to look back and forth to interpret the lines. Labels are better in almost all cases. An exception might be when the graph is too crowded to fit the labels (the example above is pushing it). Of course, you might just be graphing too much data in a small space.
To illustrate the second reason labels are more usable, consider the graph in grayscale.
If the graph were printed on a black-and-white printer, or viewed by a user with color-deficient vision, they'd be unsure how to match the key with the lines.
Legends are the rule in business because Microsoft Excel inserts them automatically into graphs. In this case, resist accepting the default. Use dedicated graphing software with your data, or just edit your Excel graph to label each series on the chart.