We report $^{51}$V nuclear magnetic resonance (NMR) studies on single crystals of the multiferroic material FeVO$_4$. The high-temperature Knight shift shows Curie-Weiss behavior, $^{51}K = a/(T + theta)$, with a large Weiss constant $theta approx$ 116 K. However, the $^{51}$V spectrum shows no ordering near these temperatures, splitting instead into two peaks below 65 K, which suggests only short-ranged magnetic order on the NMR time scale. Two magnetic transitions are identified from peaks in the spin-lattice relaxation rate, $1/^{51}T_1$, at temperatures $T_{N1} approx$ 19 K and $T_{N2} approx$ 13 K, which are lower than the estimates obtained from polycrystalline samples. In the low-temperature incommensurate spiral state, the maximum ordered moment is estimated as 1.95${mu}_B$/Fe, or 1/3 of the local moment. Strong low-energy spin fluctuations are also indicated by the unconventional power-law temperature dependence $1/^{51}T_1 propto T^2$. The large Weiss constant, short-range magnetic correlations far above $T_{N1}$, small ordered moment, significant low-energy spin fluctuations, and incommensurate ordered phases all provide explicit evidence for strong magnetic frustration in FeVO$_4$.