1570s, "one who is in pursuit of the same object as another;" 1640s, "one who emulates or strives to equal or exceed another" in some way; from Latin rivalis "a rival, adversary in love; neighbor," originally, "of the same brook," from rivus "brook" (from PIE root *rei- "to run, flow").
The sense evolution seems to be based on the competitiveness of neighbors: "one who uses the same stream," or "one on the opposite side of the stream," hence in various ways "one who is in pursuit of the same object or resource as another."
A secondary sense in Latin and sometimes in English was "associate, companion in duty," from the notion of "one having a common right or privilege with another." As an adjective, "having the same pretentions or claims, holding the position of rivals," 1580s, from the noun.
"stand in or enter into competition with another; strive to equal, emulate," c. 1600, from rival (n.). Related: Rivaled; rivaling.