We investigate the luminosity evolution of the host galaxies of radio-loud active galactic nuclei (AGNs) through Hubble Space Telescope imaging of 72 BL Lac objects, including new Space Telescope Imaging Spectrograph (STIS) imaging of nine z > 0.6 BL Lacs. With their intrinsically low accretion rates and their strongly beamed jets, BL Lac objects provide a unique opportunity to probe host galaxy evolution independent of the biases and ambiguities implicit in quasar studies. We find that the host galaxies of BL Lac objects evolve strongly, consistent with passive evolution from a period of active star formation in the range 0.5 ≲ z ≲ 2.5, and inconsistent with either passive evolution from a high formation redshift or a nonevolving population. This evolution is broadly consistent with that observed in the hosts of other radio-loud AGNs and inconsistent with the flatter luminosity evolution of quiescent early-type galaxies and radio-quiet hosts. This indicates that active star formation and hence galaxy interactions are associated with the formation of radio-loud AGNs and that these host galaxies preferentially accrete less material after their formation epoch than galaxies without powerful radio jets. We discuss possible explanations for the link between merger history and the incidence of a radio jet. © 2005. The American Astronomical Society. All rights reserved.