legality (n.)

mid-15c. "of or pertaining to the law," from Old French légal "legal" (14c.) or directly from Latin legalis "pertaining to the law," from lex (genitive legis) "an enactment; a precept, regulation, principle, rule; formal proposition for a law, motion, bill; a contract, arrangement, contrivance." This probably is related to legere "to gather," from PIE root *leg- (1) "to collect, gather," with derivatives meaning "to speak (to 'pick out words')." Perhaps the noun is from the verb on the notion of "a collection of rules," but de Vaan seems to imply that the evolution is the reverse:

The verb legare and its compounds all have a meaning which involves a 'task, assignment,' and can therefore be interpreted as derivatives of lex 'law.' The [Proto-Italic] root noun *leg- 'law' can be interpreted as a 'collection' of rules. Whether the root noun existed already in PIE is uncertain for lack of precise cognates.

Sense of "permitted by law" is from 1640s. Related: Legally. Not etymologically related to law (n.), q.v. The usual Old French form was leial, loial (see leal, loyal). Legal tender "money which the creditor is bound by law to accept" is from 1740 (see tender (n.2)). A legal holiday (1867) is one established by statute or proclamation and during which government business is usually suspended.