We report the observation of entanglement between a single trapped atom and a single photon at remote locations. The degree of coherence of the entangled atom-photon pair is verified via appropriate local correlation measurements, after communicating the photon via an optical fiber link of 300 m length to a receiver 3.5 m apart. In addition, we measured the temporal evolution of the atomic density matrix after projecting the atom via a state measurement of the photon onto several well-defined spin states. We find that the state of the single atom dephases on a time scale of 150 micros, which represents an important step towards long-distance quantum networking with individual neutral atoms.