In spite of the vast literature on the subject of first order Electroweak Phase Transitions (EWPTs), which can provide the necessary conditions for generating the Baryon Asymmetry in the Universe, fermion-induced EWPTs still remain a rather uncharted territory. In this paper, we consider a simple fermionic extension of the Standard Model involving one $SU(2)_L$ doublet and two $SU(2)_L$ singlet Vector-Like Leptons, strongly coupled to the Higgs boson and with masses close to the TeV scale. We show how such a simple scenario can give rise to a non-trivial thermal history of the Universe, involving strongly first order multistep phase transitions occurring at temperatures close to the electroweak scale. Finally, we investigate the distinct Gravitational Wave (GW) signatures of these phase transitions at future space--based GW detectors, such as LISA, DECIGO, and BBO, and briefly discuss the possible LHC signatures of the Vector-Like Leptons.