We have prepared and detected quantum coherences of trapped cesium atoms with long dephasing times. Controlled transport by an “optical conveyor belt” over macroscopic distances preserves the atomic coherence with slight reduction of coherence time. The limiting dephasing effects are experimentally identified, and we present an analytical model of the reversible and irreversible dephasing mechanisms. Our experimental methods are applicable at the single-atom level. Coherent quantum bit operations along with quantum state transport open the route towards a “quantum shift register” of individual neutral atoms.