The BL Lacertae object Markarian 501 was identified as a source of γ-ray emission at the Whipple Observatory in 1995 March. Here we present a flux variability analysis on several timescales of the 233 hr data set accumulated over 213 nights (from March 1995 to July 1998) with the Whipple Observatory 10 m atmospheric Cerenkov imaging telescope. In 1995, with the exception of a single night, the flux from Markarian 501 was constant on daily and monthly timescales and had an average flux of only 10% that of the Crab Nebula, making it the weakest very high energy 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 γ-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 timescales shorter than 1 day. Significant hour-scale variability was present in the 1997 data, with the shortest, observed on MJD 50,607, having a doubling time of ~2 hr. 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 timescales, behavior that has not been seen from Markarian 421 so far.