Abstract There are now, in principle, a limitless number of hybrid van der Waals (vdW) heterostructures that can be built from the rapidly growing number of 2D layers. The key question is how to explore this vast parameter space in a practical way. Computational methods can guide experimental work. However, even the most efficient electronic structure methods such as density functional theory, are too time consuming to explore more than a tiny fraction of all possible hybrid 2D materials. A combination of density functional theory (DFT) and machine learning techniques provide a practical method for exploring this parameter space much more efficiently than by DFT or experiments. As a proof of concept, this methodology is applied to predict the interlayer distance and band gap of bilayer heterostructures. The methods quickly and accurately predict these important properties for a large number of hybrid 2D materials. This work paves the way for rapid computational screening of the vast parameter space of vdW heterostructures to identify new hybrid materials with useful and interesting properties.