1590s "to banish (someone), send to an obscure or remote place, send away or out of the way," from Latin relegatus, past participle of relegare "remove, dismiss, banish, send away, schedule, put aside," from re- "back" (see re-) + legare "send as a deputy, send with a commission, charge, bequeath," which is possibly literally "engage by contract" and related to lex (genitive legis) "contract, law" (from PIE root *leg- (1) "to collect, gather").
All senses are from a specific meaning in Roman law: "send into exile, cause to move a certain distance from Rome for a certain period." The meaning "place (someone) in a position of inferiority" is recorded from 1790. Of subjects, things, etc., "assign to some specific category, domain, etc.," by 1866. Related: Relegated; relegating; relegable.
[Relegatio] allowed the expulsion of a citizen from Rome by magisterial decree. All examples of relegation were accomplished by magistrates with imperium, and lesser magistrates probably did not possess this power. Any number of individuals could be relegated under a single decree, and they even could be directed to relocate to a specific area. This act was generally used to remove undesirable foreigners from Rome, as when Greek philosophers were expelled from Rome in 161 and two Epicureans, Philiscus and Alcaeus, were banished seven years later. [Gordan P. Kelly, "A History of Exile in the Roman Republic," Cambridge: 2006]