Nonlinear electron-acoustic solitary waves (EASWs) are studied using Sagdeev's pseudo-potential technique in a collisionless unmagnetized plasma consisting of a cold electron fluid, nonthermal hot electrons and stationary ions. It is shown that the presence of fast nonthermal electrons may modify the parametric region where electron-acoustic solitons may exist. Our investigation is of wide relevance to astronomers and space scientists working on interstellar space plasmas.