The recent detection of TeV γ-rays from the microquasar LS 5039 by HESS is one of the most exciting discoveries of observational gamma-ray astronomy in the very high energy regime. This result clearly demonstrates that X-ray binaries with relativistic jets (microquasars) are sites of effective acceleration of particles (electrons and/or protons) to multi-TeV energies. Whether the γ-rays are of hadronic or leptonic origin is a key issue related to the origin of Galactic Cosmic Rays. We discuss different possible scenarios for the production of γ-rays, and argue in favor of hadronic origin of TeV photons, especially if they are produced within the binary system. If so, the detected γ-rays should be accompanied by a flux of high energy neutrinos emerging from the decays of π± mesons produced at pp and/or pγ interactions. The flux of TeV neutrinos, which can be estimated on the basis of the detected TeV γ-ray flux, taking into account the internal γγ → e+ e− absorption, depends significantly on the location of γ-ray production region(s). The minimum neutrino flux above 1 TeV is expected to be at the level of 10−12 cm−2s−1; however, it could be up to a factor of 100 larger. The detectability of the signal of multi-TeV neutrinos significantly depends on the high energy cutoff in the spectrum of parent protons; if the spectrum of accelerated protons continues to 1 PeV and beyond, the predicted neutrino fluxes can be probed by the planned km3-scale neutrino detector.