Streaming services for music are growing worldwide, and the Nordic countries are leading the way. In Norway, streaming represented 88 percent of digital music revenues in 2014, as opposed to 23 percent globally. In essence, streaming services offer subscribers access to vast databases of music, and offer artists new means of exposure and sources of revenue. This article argues that the possibility of musical discovery is essential to these services’ distribution model. It examines the provisions for exploration through streaming, pointing to automated algorithms and human curation as key devices. It then collects quantitative data on the presentation of music via a Norwegian service (WiMP/Tidal) and qualitative findings from interviews with consumers about their experiences with music streaming. Key discrepancies arise between the promise and the reality of streamed-music discovery, both for artists seeking new fans (and funds) and for audiences expecting streaming to supersede existing forms of musical exploration.