We have studied, using reflection high energy electron diffraction (RHEED), the initial growth stages of ZnSe layers grown by molecular beam epitaxy (MBE) on GaAs exhibiting various surface terminations. The structural quality of the ZnSe layers was assessed by transmission electron microscopy (TEM). We have observed a preference for two-dimensional nucleation on As-terminated GaAs substrates, whether epitaxial or bulk. On Ga-terminated surfaces a transitional region of three-dimensional growth forms initially. The different behaviors may reflect the electronic imbalance present in the growing GaAs/ZnSe interface. While defect free, thin layers of ZnSe are best obtained on As-terminated GaAs, the initial three-dimensional growth region on the Ga-rich surfaces appears to reduce the density of extended faults formed in thick ZnSe layers due to the lattice mismatch with GaAs.