We present powder and single-crystal neutron diffraction and bulk measurements of the Kagome-staircase compound Ni3V2O8 (NVO) in fields up to 8.5T applied along the c-direction. (The Kagome plane is the a-c plane.) This system contains two types of Ni ions, which we call spine and cross-tie. Our neutron measurements can be described with the paramagnetic space group Cmca for T < 15K and each observed magnetically ordered phase is characterized by the appropriate irreducible representation(s). Our zero-field measurements show that at T_PH=9.1K NVO undergoes a transition to an incommensurate order which is dominated by a longitudinally-modulated structure with the spine spins mainly parallel to the a-axis. Upon further cooling, a transition is induced at T_HL=6.3K to an elliptically polarized incommensurate structure with both spine and cross-tie moments in the a-b plane. At T_LC=4K the system undergoes a first-order phase transition, below which the magnetic structure is a commensurate antiferromagnet with the staggered magnetization primarily along the a-axis and a weak ferromagnetic moment along the c-axis. A specific heat peak at T_CC=2.3K indicates an additional transition, which we were however not able to relate to a change of the magnetic structure. Neutron, specific heat, and magnetization measurements produce a comprehensive temperature-field phase diagram. The symmetries of the two incommensurate magnetic phases are consistent with the observation that only one phase has a spontaneous ferroelectric polarization. All the observed magnetic structures are explained theoretically using a simplified model Hamiltonian, involving competing nearest- and next-nearest-neighbor exchange interactions, spin anisotropy, Dzyaloshinskii-Moriya and pseudo-dipolar interactions.