The BL Lacertae object Markarian 501 was identified as a source of gamma-ray emission at the Whipple Observatory in March 1995. Here we present a flux variability analysis on several times-scales of the 233 hour data set accumulated over 213 nights (from March 1995 to July 1998) with the Whipple Observatory 10 m atmospheric Cherenkov imaging telescope. In 1995, with the exception of a single night, the flux from Markarian 501 was constant on daily and monthly time-scales and had an average flux of only 10% that of the Crab Nebula, making it the weakest VHE source detected to date. In 1996, the average flux was approximately twice the 1995 flux and showed significant month-to-month variability. No significant day-scale variations were detected. The average gamma-ray flux above ~350 GeV in the 1997 observing season rose to 1.4 times that of the Crab Nebula -- 14 times the 1995 discovery level -- allowing a search for variability on time-scales shorter than one day. Significant hour-scale variability was present in the 1997 data, with the shortest, observed on MJD 50607, having a doubling time of ~2 hours. In 1998 the average emission level decreased considerably from that of 1997 (to ~20% of the Crab Nebula flux) but two significant flaring events were observed. Thus, the emission from Markarian 501 shows large amplitude and rapid flux variability at very high energies as does Markarian 421. It also shows large mean flux level variations on year-to-year time-scales, behaviour which has not been seen from Markarian 421 so far.