(abridged) We present near-infrared Ks-band imaging of 13 high redshift (0.6 < z < 1.3) BL Lac objects. We clearly detect the host in eight objects, and marginally in three others. In all cases, the host galaxy is well represented by an r^1/4 surface brightness law. The host galaxies of high redshift BL Lacs are large (<R(e)> ~7 kpc) and very luminous (<M(K)> = -27.9+-0.7), ~3 mag brighter than L*, and ~1 mag brighter than brightest cluster galaxies. They are also ~1 mag brighter than low redshift radio galaxies and appear to deviate from their K-z relationship. On the other hand, the high luminosities agree with the few optical studies of high redshift BL Lac hosts. The nuclear luminosity and the nucleus-galaxy luminosity ratio of the high redshift BL Lacs are much larger than those in low redshift BL Lacs. This may be due to either a higher intrinsic nuclear luminosity, or enhanced luminosity because of strong beaming. Contrary to what is observed in low redshift BL Lacs, the luminosities of the host galaxy and of the nucleus are fairly well correlated, as expected from the black hole mass - bulge luminosity relationship. High redshift BL Lacs radiate with a wide range of power with respect to their Eddington luminosity, and this power is intermediate between those in nearby BL Lacs and in luminous radio-loud quasars. The high redshift BL Lac host galaxies appear to be ~2 mag brighter than those at low redshift. This is likely due to a strong selection effect in the surveys of BL Lacs that makes observable only the most luminous sources at z > 0.5 and produces a correlation between the nuclear and the host luminosity. However, this may also suggest strong luminosity evolution which is inconsistent with a simple passive evolution of the host galaxies, and requires a contribution from relatively recent star formation episodes.