Old English belyfan "to have faith or confidence" (in a person), earlier geleafa (Mercian), gelefa (Northumbrian), gelyfan (West Saxon), from Proto-Germanic *ga-laubjan "to believe," perhaps literally "hold dear (or valuable, or satisfactory), to love" (source also of Old Saxon gilobian "believe," Dutch geloven, Old High German gilouben, German glauben), ultimately a compound based on PIE root *leubh- "to care, desire, love" (see belief).
Meaning "be persuaded of the truth of" (a doctrine, system, religion, etc.) is from mid-13c.; meaning "credit upon the grounds of authority or testimony without complete demonstration, accept as true" is from early 14c. General sense "be of the opinion, think" is from c. 1300. Related: Believed (formerly occasionally beleft); believing.
The form beleeve was common till 17c., the spelling then changed, perhaps by influence of relieve, etc. To believe on instead of in was more common in 16c. but now is a peculiarity of theology; believe of also sometimes was used in 17c. Expression believe it or not attested by 1874; Robert Ripley's newspaper cartoon of the same name is from 1918. Emphatic you better believe attested from 1854.