We report on the spectroscopic confirmation of a large scale structure around the luminous, z=6.31 QSO SDSS~J1030+0524, that is powered by a billion solar mass black hole. The structure is populated by at least six members, four Lyman Break Galaxies (LBGs) and two Lyman Alpha Emitters (LAEs). The four LBGs have been identified among a sample of 21 i-band dropouts with z{AB}<25.5 selected up to projected separations of 5 physical Mpc (15 arcmin) from the QSO. Their redshifts have been determined through up to 8hr-long multi-object spectroscopic observations at 8-10m class telescopes. The two LAEs have been identified in a 6hr VLT/MUSE observation centered on the QSO. The redshifts of the six galaxies cover the range 6.129-6.355. Assuming that peculiar velocities are negligible, this range corresponds to radial separations of +/-5 physical Mpc from the QSO, that is comparable to the projected scale of the observed LBG distribution on the sky. We conservatively estimate that this structure is significant at >3.5 sigma level, and that the level of the galaxy overdensity is at least 1.5-2 within the large volume sampled (~780 physical Mpc^3). The spectral properties of the six member galaxies (Lyalpha strength and UV luminosity) are similar to those of field galaxies at similar redshifts. This is the first spectroscopic identification of a galaxy overdensity around a super-massive black hole in the first billion years of the Universe. Our finding lends support to the idea that the most distant and massive black holes form and grow within massive (>10^{12} Msun) dark matter halos in large scale structures, and that the absence of earlier detections of such systems was likely due to observational limitations.