Summary: We show how the Newton-Cartan formulation of Newtonian gravity can be obtained from gauging the Bargmann algebra, i.e. the centrally extended Galilean algebra. In this gauging procedure several curvature constraints are imposed. These convert the spatial (time) translational symmetries of the algebra into spatial (time) general coordinate transformations and make the spin connection gauge fields dependent. In addition we require two independent vielbein postulates for the temporal and spatial directions. In the final step we impose an additional curvature constraint to establish the connection with the (on-shell) Newton-Cartan theory. We discuss a few extensions of our work that are relevant in the context of the AdS-CFT correspondence.