Social media like Facebook or Twitter have become an entry point to news for many readers. In that scenario, the headline is the most prominent — and often the only visible — part of the news article. We propose a novel task of using only headlines to predict the popularity of news articles. The prediction model is evaluated on headlines from two major broadsheet news outlets — The Guardian and New York Times. We significantly improve over several baselines, noting differences in the model performance between Facebook and Twitter.