A large radio outburst from Sgr A* was observed during the VLA weekly monitoring program at 2 cm, 1.3 cm and 7 mm, nearly coincident with the brightest X-ray flare detected to date with the XMM-Newton X-ray Observatory on 2002-10-03. The flux density of 1.9+/-0.2 Jy measured at 7 mm exceeds the mean value (1.00+/-0.01 Jy) by a factor of 2, one of the two highest increases observed during the past three years (June 2000-October 2003), while less significant increases in flux densities were observed at 1.3 cm and 2 cm. The radio observation started 13.5 hrs after the onset of the X-ray flare (which had occurred over a 45 min duration) and continued for 1.3 hrs. During the observation, there was no significant (<3σ) change in the radio flux densities at all the three wavelengths, indicating that the radio outburst varied on a timescale of >1hr. A spectral index of α=2.4+0.3-0.6 (S να) was derived for the outburst component, consistent with an optically thick nonthermal synchrotron source. These results suggest that energetic electrons responsible for the radio outburst might be produced via a process associated with the X-ray flare, then transported to large radii, producing the observed radio outburst. The observation is the first evidence for a correlated variation in the radio and X-ray emissions from Sgr A*.