We report the observation of an oscillatory dependence of the low-temperature resistance of individual single-crystal bismuth nanowires on the Aharonov-Bohm phase of the magnetic flux threading the wire. 55 and 75 nm wires were investigated in magnetic fields of up to 14 T. For 55 nm nanowires, longitudinal magnetoresistance periods of 0.8 and 1.6 T that were observed at magnetic fields over 4 T are assigned to h/2e to h/e magnetic flux modulation. The same modes of oscillation were observed in 75 nm wires. The observed effects are consistent with models of the Bi surface where surface states give rise to a significant population of charge carriers of high effective mass that form a highly conducting tube around the nanowire. In the 55 nm wires, the Fermi energy of the surface band is estimated to be 18 meV. An interpretation of the magnetoresistance oscillations in terms of a subband structure in the surface state band caused by quantum interference in the tube is presented.