"A substantial entity believed to be that in each person which lives, feels, thinks and wills" [Century Dictionary], Old English sawol "spiritual and emotional part of a person, animate existence; life, living being," from Proto-Germanic *saiwalō (source also of Old Saxon seola, Old Norse sala, Old Frisian sele, Middle Dutch siele, Dutch ziel, Old High German seula, German Seele, Gothic saiwala), of uncertain origin.
Sometimes said to mean originally "coming from or belonging to the sea," because that was supposed to be the stopping place of the soul before birth or after death [Barnhart]; if so, it would be from Proto-Germanic *saiwaz (see sea). Klein explains this as "from the lake," as a dwelling-place of souls in ancient northern Europe.
Meaning "spirit of a deceased person" is attested in Old English from 971. As a synonym for "person, individual, human being" (as in every living soul) it dates from early 14c. Soul-searching (n.) is attested from 1871, from the phrase used as a present-participle adjective (1610s). Distinguishing soul from spirit is a matter best left to theologians.