"not accomplished," c.1300, from un- (1) + done. The same word meaning "destroyed" is recorded from mid-14c., past participle adjective from undo.
Old English undon "to unfasten and open" (a window or door), "to unfasten by releasing from a fixed position," from un- (2) + do (v.). The notion is of "to annul something that was done." Related: Undone; undoing.