late 14c., "cross out with lines, draw lines across (something written) so as to deface," from Anglo-French and Old French canceler, from Latin cancellare "to make like a lattice," which in Late Latin took on especially a sense "cross out something written" by marking it with crossed lines, from cancelli, plural of *cancellus (n.) "lattice, grating," diminutive of cancer "crossed bars, a lattice," a variant of carcer "prison" (see incarceration).
Figurative use, "to nullify (an obligation, etc.)" is from mid-15c. Related: Canceled (also cancelled); cancelling.