LS 5039 is the only X-ray binary persistently detected at TeV energies by the Cherenkov HESS telescope. It is moreover a gamma-ray emitter in the GeV and possibly MeV energy ranges. To understand important aspects of jet physics, like the magnetic field content or particle acceleration, and emission processes, such as synchrotron and inverse Compton (IC), a complete modeling of the multiwavelength data is necessary. LS 5039 has been detected along almost all the electromagnetic spectrum thanks to several radio, infrared, optical and soft X-ray detections. However, hard X-ray detections above 20 keV have been so far elusive and/or doubtful, partly due to source confusion for the poor spatial resolution of hard X-ray instruments. We report here on deep (300 ksec) serendipitous INTEGRAL hard X-ray observations of LS 5039, coupled with simultaneous VLA radio observations. We obtain a 20-40 keV flux of 1.1 +/- 0.3 mCrab (5.9 (+/-1.6) X 10^{-12} erg cm^{-2} s^{-1}), a 40-100 keV upper limit of 1.5 mCrab (9.5 x 10^{-12} erg cm^{-2}s^{-1}), and typical radio flux densities of about 25 mJy at 5GHz. These hard X-ray fluxes are significantly lower than previous estimates obtained with BATSE in the same energy range but, in the lower interval, agree with extrapolation of previous RXTE measurements. The INTEGRAL observations also hint to a break in the spectral behavior at hard X-rays. A more sensitive characterization of the hard X-ray spectrum of LS 5039 from 20 to 100 keV could therefore constrain key aspects of the jet physics, like the relativistic particle spectrum and the magnetic field strength. Future multiwavelength observations would allow to establish whether such hard X-ray synchrotron emission is produced by the same population of relativistic electrons as those presumably producing TeV emission through IC.