We present the discovery of optical/X-ray flux correlations on rapid time-scales in the low/hard state of the Galactic black hole GX339-4. The source had recently emerged from outburst and was associated with a relatively faint counterpart with mag V ~ 17. The optical [Very Large Telescope (VLT)/ULTRACAM] and X-ray (Rossi X-ray Timing Explorer) data show a clear positive cross-correlation function (CCF) signal, with the optical peak lagging X-rays by ~150 ms, preceded by a shallow rise and followed by a steep decline along with broad anticorrelation dips. An examination of the light curves shows that the main CCF features are reproduced in superpositions of flares and dips. The CCF peak is narrow and the X-ray autocorrelation function (ACF) is broader than the optical ACF, arguing against reprocessing as the origin for the rapid optical emission. X-ray flaring is associated with spectral hardening, but no corresponding changes are detected around optical peaks and dips. The variability may be explained in the context of synchrotron emission with interaction between a jet and a corona. The complex CCF structure in GX 339-4 has similarities to that of another remarkable X-ray binary XTE J1118+480, in spite of showing a weaker maximum strength. Such simultaneous multiwavelength, rapid timing studies provide key constraints for modelling the inner regions of accreting stellar sources. Based on observations carried out in ESO programmes 079.D-0535 and 279.D-5021, and Rossi X-ray Timing Explorer proposal number 93119. E-mail: pg [at] crab.riken.jp (pg[at]crab[dot]riken[dot]jp)