Gamma-ray binaries are stellar systems containing a neutron star or black hole, with gamma-ray emission produced by an interaction between the components. These systems are rare, even though binary evolution models predict dozens in our Galaxy. A search for gamma-ray binaries with the Fermi Large Area Telescope (LAT) shows that 1FGL J1018.6-5856 exhibits intensity and spectral modulation with a 16.6-day period. We identified a variable x-ray counterpart, which shows a sharp maximum coinciding with maximum gamma-ray emission, as well as an O6V((f)) star optical counterpart and a radio counterpart that is also apparently modulated on the orbital period. 1FGL J1018.6-5856 is thus a gamma-ray binary, and its detection suggests the presence of other fainter binaries in the Galaxy.