In 2000 Constantin showed that the incompressible Euler equations can be written in an Eulerian-Lagrangian form which involves the back-to-labels map (the inverse of the trajectory map for each fixed time). In the same paper a local existence result is proved in certain Holder spaces $C^{1,mu}$. We review the Eulerian-Lagrangian formulation of the equations and prove that given initial data in $H^s$ for $ngeq2$ and $s>frac{n}{2}+1$, a unique local-in-time solution exists on the $n$-torus that is continuous into $H^s$ and $C^1$ into $H^{s-1}$. These solutions automatically have $C^1$ trajectories. The proof here is direct and does not appeal to results already known about the classical formulation. Moreover, these solutions are regular enough that the classical and Eulerian-Lagrangian formulations are equivalent, therefore what we present amounts to an alternative approach to some of the standard theory.