We construct the open-string scattering amplitudes for neutrino-gluon collisions and evaluate the high energy neutrino-nucleon scattering cross section via string state excitations in the TeV string-scale scenario. We find that the neutrino-gluon scattering is the dominant contribution, 5-10 times larger than neutrino-quark processes, though black hole production may be larger than the string contribution at higher energies. We illustrate the observability of the string signal at the Auger Observatory and the IceCube neutrino telescope for a string scale about 1 TeV.