Supernova SN 1998bw exploded in the same direction and at the same time as the gamma-ray burst GRB 980425. Here we report radio observations of this type Ic supernova, beginning 4 days after the gamma-ray burst. At its peak the radio source is the most luminous ever seen from a supernova, nu L_nu = 4 x 103̂8 erg/s at 5 GHz. More remarkably, the traditional synchrotron interpretation of the radio emission requires that the radio source be expanding at an apparent velocity of at least twice the speed of light, indicating that this supernova was accompanied by a shock wave moving at relativistic speed. The energy U_e associated with the radio-emitting relativistic electrons must lie between 109̂ erg <U_e< 10^ ̂erg, and thus represents a significant fraction of the total kinetic energy åisebox-0.5ex 10^5êrg associated with supernova explosions. The presence of a relativistic shock in SN 1998bw suggests a physical connection with the gamma-ray burst GRB 980425. We argue that this represents a second class of gamma-ray burst, with much lower emitted energy i̊sebox-0.5ex 10^48r̂g in gamma-rays than the two powerful rs̊ebox-0.5ex 10^53 ĝ high-redshift gamma-ray bursts previously identified.