Up to date all spin transport experiments on graphene were done in a semi-classical regime, disregarding quantum transport properties such as phase coherence and interference. Here we show that in a quantum coherent graphene nanostructure the non-local voltage is strongly modulated. Using non-local measurements, we separate the signal in spin dependent and spin independent contributions. We show that the spin dependent contribution is about two orders of magnitude larger than the spin independent one, when corrected for the finite polarization of the electrodes. The non-local spin signal is not only strongly modulated but also changes polarity as a function of the applied gate voltage. By locally tuning the carrier density in the constriction via a side gate electrode we show that the constriction plays a major role in this effect. Our results show the potential of quantum coherent graphene nanostructures for the use in future spintronic devices.