A time-dependent formulation for electron-hole excitations in extended finite systems, based on the Bethe-Salpeter equation (BSE), is developed using a stochastic wave function approach. The time-dependent formulation builds on the connection between time-dependent Hartree-Fock (TDHF) theory and the configuration-interaction with single substitution (CIS) method. This results in a time-dependent Schrödinger-like equation for the quasiparticle orbital dynamics based on an effective Hamiltonian containing direct Hartree and screened exchange terms, where screening is described within the random-phase approximation (RPA). To solve for the optical-absorption spectrum, we develop a stochastic formulation in which the quasiparticle orbitals are replaced by stochastic orbitals to evaluate the direct and exchange terms in the Hamiltonian as well as the RPA screening. This leads to an overall quadratic scaling, a significant improvement over the equivalent symplectic eigenvalue representation of the BSE. Application of the time-dependent stochastic BSE (TDsBSE) approach to silicon and CdSe nanocrystals up to size of 3000 electrons is presented and discussed.