Recently a metallic state was discovered at the interface between insulating oxides, most notably LaAlO3 and SrTiO3. Properties of this two-dimensional electron gas (2DEG) have attracted significant interest due to its potential applications in nanoelectronics. Control over this carrier density and mobility of the 2DEG is essential for applications of these novel systems, and may be achieved by epitaxial strain. However, despite the rich nature of strain effects on oxide materials properties, such as ferroelectricity, magnetism, and superconductivity, the relationship between the strain and electrical properties of the 2DEG at the LaAlO3/SrTiO3 heterointerface remains largely unexplored. Here, we use different lattice constant single crystal substrates to produce LaAlO3/SrTiO3 interfaces with controlled levels of biaxial epitaxial strain. We have found that tensile strained SrTiO3 destroys the conducting 2DEG, while compressively strained SrTiO3 retains the 2DEG, but with a carrier concentration reduced in comparison to the unstrained LaAlO3/SrTiO3 interface. We have also found that the critical LaAlO3 overlayer thickness for 2DEG formation increases with SrTiO3 compressive strain. Our first-principles calculations suggest that a strain-induced electric polarization in the SrTiO3 layer is responsible for this behavior. It is directed away from the interface and hence creates a negative polarization charge opposing that of the polar LaAlO3 layer. This both increases the critical thickness of the LaAlO3 layer, and reduces carrier concentration above the critical thickness, in agreement with our experimental results. Our findings suggest that epitaxial strain can be used to tailor 2DEGs properties of the LaAlO3/SrTiO3 heterointerface.