To understand and control the basic functions of physical, chemical and biological processes from micron to nano-meter scale, an instrument capable of visualizing transient structural changes of inhomogeneous materials with atomic spatial and temporal resolutions, is required. One such technique is femtosecond electron microdiffraction, in which a short electron pulse with femtosecond-scale duration is focused into a micron-scale spot and used to obtain diffraction images to resolve ultrafast structural dynamics over a localized crystalline domain. In this letter, we report the experimental demonstration of time-resolved mega-electron-volt electron microdiffraction which achieves a 5 μm root-mean-square (rms) beam size on the sample and a 110 fs rms temporal resolution. Using pulses of 10k electrons at 4.2 MeV energy with a normalized emittance 3 nm-rad, we obtained high quality diffraction from a single 10 μm paraffin (C44H90) crystal. The phonon softening mode in optical-pumped polycrystalline Bi was also time-resolved, demonstrating the temporal resolution limits of the instrument. In conclusion, this new characterization capability will open many research opportunities in material and biological sciences.