Pada hari pertamanya di sekolah menengah pertama, Mato Kuroi bertemu dengan Yomi Takanashi. Meskipun Yomi awalnya terkejut dengan kepribadian Mato yang lugas, pasangan ini dengan cepat menjadi teman dan mulai menghabiskan waktu bersama setiap hari. Sebagai tanda persahabatan mereka, Mato memberi Yomi pesona ponsel—bintang biru, identik dengan miliknya.
Namun, ketika keduanya memasuki tahun kedua, hubungan mereka mulai berubah. Ditempatkan di kelas yang berbeda, Mato mulai menghabiskan lebih banyak waktu dengan Yuu Koutari sebagai gantinya, seorang gadis yang dia temui melalui tim bola basket. Faktanya, mantan sahabat itu sangat terpisah sehingga Mato tidak dapat menemukan Yomi di mana pun, seolah-olah dia telah menghilang sepenuhnya.
Di tempat lain, Black★Rock Shooter sedang dalam pencarian untuk mengalahkan Dead Master. Keduanya, meskipun bertentangan, memiliki hubungan yang tidak seperti Mato dan Yomi. Saat cerita mereka mulai terlintas, tampaknya hilangnya Yomi mungkin ada hubungannya dengan pesona berbentuk bintang biru dan penembak legendaris itu sendiri.