In heteroepitaxy, lattice mismatch between the deposited material and the underlying surface strongly affects nucleation and growth processes. The effect of mismatch is well studied in atoms with growth kinetics typically dominated by bond formation with interaction lengths on the order of one lattice spacing. In contrast, less is understood about how mismatch affects crystallization of larger particles, such as globular proteins and nanoparticles, where interparticle interaction energies are often comparable to thermal fluctuations and are short ranged, extending only a fraction of the particle size. Here, using colloidal experiments and simulations, we find particles with short-range attractive interactions form crystals on isotropically strained lattices with spacings significantly larger than the interaction length scale. By measuring the free-energy cost of dimer formation on monolayers of increasing uniaxial strain, we show the underlying mismatched substrate mediates an entropy-driven attractive interaction extending well beyond the interaction length scale. Remarkably, because this interaction arises from thermal fluctuations, lowering temperature causes such substrate-mediated attractive crystals to dissolve. Such counterintuitive results underscore the crucial role of entropy in heteroepitaxy in this technologically important regime. Ultimately, this entropic component of lattice mismatched crystal growth could be used to develop unique methods for heterogeneous nucleation and growth of single crystals for applications ranging from protein crystallization to controlling the assembly of nanoparticles into ordered, functional superstructures. In particular, the construction of substrates with spatially modulated strain profiles would exploit this effect to direct self-assembly, whereby nucleation sites and resulting crystal morphology can be controlled directly through modifications of the substrate.