The continuously growing use of digital services has provided social scientists with an expanding reservoir of data, potentially holding valuable insights into human behavior and social systems. This has often been associated with the terms “big data” and “computational social science.” Using such data, social scientists have argued, will enable us to better understand social, political, and economic life. Yet this new data type comes not only with promises but with challenges as well. These include developing standards for data collection, preparation, analysis, and reporting; establishing more systematic links between established theories within the existing body of research in the social sciences; and moving away from proofs-of-concepts toward the systematic development and testing of hypotheses. In this article, we map these promises and challenges in detail and introduce five highly innovative contributions collected in this special issue. These articles illustrate impressively the potential of digital trace data in the social science all the while remaining conscious of its pitfalls.