c. 1400, prevailen, "be successful; be efficacious," from Old French prevaleir (Modern French prévaloir) and directly from Latin praevalere "be stronger or more able, have greater power," from prae "before" (see pre-) + valere "have power, be strong" (from PIE root *wal- "to be strong").
The spelling in English perhaps has been influenced by avail. The meaning "have or exert superior influence" is from mid-15c. (to prevail upon "succeed in persuading" is by 1570s). The sense of "be in force, be prevalent or current" is by 1776. Related: Prevailed; prevailing.