In the past, leading newspaper companies and broadcasters were the sole distributors of news articles, and thus news consumers simply received news articles from those outlets at regular intervals. However, the growth of social media and smart devices led to a considerable change in this traditional relationship between news providers and consumers. Hundreds of thousands of news articles are now distributed on social media, and consumers can access those articles at any time via smart devices. This has meant that news providers are under pressure to find ways of engaging the attention of consumers. This paper provides a novel solution to this problem by identifying attractive headlines as a gateway to news articles. We first perform one of the first investigations of news headlines on a major viral medium. Using our investigation as a basis, we also propose a learning-to-rank method that suggests promising news headlines. Our experiments with 2,000 news articles demonstrate that our proposed method can accurately identify attractive news headlines from the candidates and reveals several promising factors of making news articles go viral.