Leading theories for the presence of plate tectonics on Earth typically appeal to the role of present day conditions in promoting rheological weakening of the lithosphere. However, it is unknown whether the conditions of the early Earth were favorable for plate tectonics, or any form of subduction, and thus how subduction begins is unclear. Using physical models based on grain-damage, a grainsize-feedback mechanism capable of producing plate-like mantle convection, we demonstrate that subduction was possible on the Hadean Earth (hereafter referred to as proto-subduction or proto-plate tectonics), that proto-subduction differed from modern day plate tectonics, and that it could initiate rapidly. Scaling laws for convection with grain-damage show that, though either higher mantle temperatures or higher surface temperatures lead to slower plates, proto-subduction, with plate speeds of $\approx 1.75$ cm/yr, can still be maintained in the Hadean, even with a CO$_2$ rich primordial atmosphere. Furthermore, when the mantle potential temperature is high (e.g. above $\approx 2000$ K), the mode of subduction switches to a "sluggish subduction" style, where downwellings are drip-like and plate boundaries are diffuse. Finally, numerical models of post-magma ocean mantle convection demonstrate that proto-plate tectonics likely initiates within $\sim100$ Myrs of magma ocean solidification, consistent with evidence from Hadean zircons. After the initiation of proto-subduction, non-plate-tectonic "sluggish subduction" prevails, giving way to modern style plate tectonics as both the mantle interior and climate cool. Hadean proto-subduction may hasten the onset of modern plate tectonics by drawing excess CO$_2$ out of the atmosphere and cooling the climate.

Numerical experiments of convection with grain-damage are used to develop scaling laws for convective heat flow, mantle velocity, and plate velocity across the stagnant lid and plate-tectonic regimes. Three main cases are presented in order of increasing complexity: a simple case wherein viscosity is only dependent on grainsize, a case where viscosity depends on temperature and grainsize, and finally a case where viscosity is temperature and grainsize sensitive, and the grain-growth (or healing) is also temperature sensitive. In all cases, convection with grain-damage scales differently than Newtonian convection due to the effects of grain-damage. For the fully realistic case, numerical results show stagnant lid convection, fully mobilized convection that resembles the temperature-independent viscosity case, and partially mobile or transitional convection, depending on damage to healing ratio, Rayleigh number, and the activation energies for viscosity and healing. Applying our scaling laws for the fully realistic case to Earth and Venus we demonstrate that increasing surface temperature dramatically decreases plate speed and heat flow, essentially shutting down plate tectonics, due to increased healing in lithospheric shear zones, as proposed previously. Contrary to many previous studies, the transitional regime between the stagnant lid and fully mobilized regimes is large, and the transition from stagnant lid to mobile convection is gradual and continuous. Thus planets could exhibit a full range of surface mobility, as opposed to the bimodal distribution of fully mobile lid planets and stagnant lid planets that is typically assumed.