In the standard picture of structure formation, the first massive galaxies are expected to form at the highest peaks of the density field, which constitute the cores of massive proto-clusters. Luminous quasars (QSOs) at z~4 are the most strongly clustered population known, and should thus reside in massive dark matter halos surrounded by large overdensities of galaxies, implying a strong QSO-galaxy cross-correlation function. We observed six z~4 QSO fields with VLT/FORS exploiting a novel set of narrow band filters custom designed to select Lyman Break Galaxies (LBGs) in a thin redshift slice of Delta_z~0.3, mitigating the projection effects that have limited the sensitivity of previous searches for galaxies around z>~4 QSOs. We find that LBGs are strongly clustered around QSOs, and present the first measurement of the QSO-LBG cross-correlation function at z~4, on scales of 0.1<~R<~9 Mpc/h (comoving). Assuming a power law form for the cross-correlation function xi=(r/r0_QG)^gamma, we measure r0_QG=8.83^{+1.39}_{-1.51} Mpc/h for a fixed slope of gamma=2.0. This result is in agreement with the expected cross-correlation length deduced from measurements of the QSO and LBG auto-correlation function, and assuming a linear bias model. We also measure a strong auto-correlation of LBGs in our QSO fields finding r0_GG=21.59^{+1.72}_{-1.69} Mpc/h for a fixed slope of gamma=1.5, which is ~4 times larger than the LBG auto-correlation length in random fields, providing further evidence that QSOs reside in overdensities of LBGs. Our results qualitatively support a picture where luminous QSOs inhabit exceptionally massive (M_halo>10^12 M_sun) dark matter halos at z~4.