We present optical, X-ray, high-energy ((sic) 30 GeV) and very high energy ((sic) 100 GeV; VHE) observations of the high-frequency peaked blazar Mrk 421 taken between 2008 May 24 and June 23. A high-energy gamma-ray signal was detected by AGILE with root TS = 4.5 between June 9 and 15, with F(E > 100 MeV) = 42(-12)(+14) x 10(-8) photons cm(-2) s(-1). This flaring state is brighter than the average flux observed by EGRET by a factor of similar to 3, but still consistent with the highest EGRET flux. In hard X-rays (20-60 keV) SuperAGILE resolved a five-day flare (June 9-15) peaking at similar to 55 mCrab. SuperAGILE, RXTE/ASM and Swift/BAT data show a correlated flaring structure between soft and hard X-rays. Hints of the same flaring behavior are also detected in the simultaneous optical data provided by the GASP-WEBT. A Swift/XRT observation near the flaring maximum revealed the highest 2-10 keV flux ever observed from this source, of 2.6 x 10(-9) erg cm(-2) s(-1) (i.e. > 100 mCrab). A peak synchrotron energy of similar to 3 keV was derived, higher than typical values of similar to 0.5-1 keV. VHE observations with MAGIC and VERITAS between June 6 and 8 showed the flux peaking in a bright state, well correlated with the X-rays. This extraordinary set of simultaneous data, covering a 12-decade spectral range, allowed for a deep analysis of the spectral energy distribution as well as of correlated light curves. The gamma-ray flare can be interpreted within the framework of the synchrotron self-Compton model in terms of a rapid acceleration of leptons in the jet.