Direct imaging has only begun to inventory the population of gas giant planets on wide orbits around young stars in the solar neighborhood. Following this approach, we carried out a deep imaging survey in the near-infrared using VLT/NaCo to search for substellar companions. Here we report the discovery of a probable companion orbiting the young (10-17 Myr), dusty, early-type (A8) star HD 95086 at 56 AU in L' (3.8 mu m) images. This discovery is based on observations with more than a year time lapse. Our first epoch clearly revealed the source at similar or equal to 10 sigma, while our second epoch lacks good observing conditions, yielding a similar or equal to 3 sigma detection. Various tests were thus made to rule out possible artifacts. This recovery is consistent with the signal at the first epoch but requires cleaner confirmation. Nevertheless, our astrometric precision suggests that the companion is comoving with the star with a 3 sigma confidence level. The planetary nature of the source is reinforced by a non-detection in the Ks-band (2.18 mu m) images according to its possible extremely red Ks-L' color. Conversely, background contamination is rejected with good confidence level. The luminosity yields a predicted mass of about 4-5 M-Jup (at 10-17 Myr) using "hot-start" evolutionary models, making HD 95086 b the exoplanet with the lowest mass ever imaged around a star.