Markarian 421 was observed for about four days with BeppoSAX and the Whipple Observatory gamma-ray telescope in April 1998. A pronounced, well-defined, flare with hour-scale variability was observed simultaneously in X-rays and very high energy gamma-rays. These data provide the first evidence that the X-ray and TeV intensities are well correlated on time-scales of hours. While the rise of the flare occurred on a similar time-scale in the two wavebands, the decay of the flare was much more rapid in gamma rays, providing the first clear indication that the X-ray and gamma-ray emission may not be completely correlated in Markarian 421.