Entanglement has a central role in fundamental tests of quantum mechanics as well as in the burgeoning field of quantum information processing. Particularly in the context of quantum networks and communication, a main challenge is the efficient generation of entanglement between stationary (spin) and propagating (photon) quantum bits. Here we report the observation of quantum entanglement between a semiconductor quantum dot spin and the colour of a propagating optical photon. The demonstration of entanglement relies on the use of fast, single-photon detection, which allows us to project the photon into a superposition of red and blue frequency components. Our results extend the previous demonstrations of single-spin/single-photon entanglement in trapped ions, neutral atoms and nitrogen-vacancy centres to the domain of artificial atoms in semiconductor nanostructures that allow for on-chip integration of electronic and photonic elements. As a result of its fast optical transitions and favourable selection rules, the scheme we implement could in principle generate nearly deterministic entangled spin-photon pairs at a rate determined ultimately by the high spontaneous emission rate. Our observation constitutes a first step towards implementation of a quantum network with nodes consisting of semiconductor spin quantum bits.