There is significant recent work on coupling matter to Newton-Cartan spacetimes with the aim of investigating certain condensed matter phenomena. To this end, one needs to have a completely general spacetime consistent with local non-relativisitic symmetries which supports massive matter fields. In particular, one can not impose a priori restrictions on the geometric data if one wants to analyze matter response to a perturbed geometry. In this paper we construct such a Bargmann spacetime in complete generality without any prior restrictions on the fields specifying the geometry. The resulting spacetime structure includes the familiar Newton-Cartan structure with an additional gauge field which couples to mass. We illustrate the matter coupling with a few examples. The general spacetime we construct also includes as a special case the covariant description of Newtonian gravity, which has been thoroughly investigated in previous works. We also show how our Bargmann spacetimes arise from a suitable non-relativistic limit of Lorentzian spacetimes. In a companion paper [arXiv:1503.02680] we use this Bargmann spacetime structure to investigate the details of matter couplings, including the Noether-Ward identities, and transport phenomena and thermodynamics of non-relativistic fluids.