Majorana fermions are particles identical to their own antiparticles. They have been theoretically predicted to exist in topological superconductors. We report electrical measurements on InSb nanowires contacted with one normal (Au) and one superconducting electrode (NbTiN). Gate voltages vary electron density and define a tunnel barrier between normal and superconducting contacts. In the presence of magnetic fields of order 100 mT, we observe bound, mid-gap states at zero bias voltage. These bound states remain fixed to zero bias even when magnetic fields and gate voltages are changed over considerable ranges. Our observations support the hypothesis of Majorana fermions in nanowires coupled to superconductors.