past participle of do (v.); from Old English past participle gedon (a vestige of the prefix is in ado). As a past-participle adjective meaning "completed, finished, performed, accomplished" from early 15c. As a word of acceptance of a deal or wager, 1590s.
U.S. Southern use of done in phrases such as done gone (or "Octopots done got Albert!") is attested by 1827, according to OED: "a perfective auxiliary or with adverbial force in the sense 'already; completely.' " Century Dictionary writes that it was "originally causal after have or had, followed by an object infinitive ; in present use the have or had is often omitted and the infinitive turned into a preterit, leaving done as a mere preterit sign" and calls it "a characteristic of negro idiom."
To be done in "exhausted" is by 1917. Slang done for "doomed" is by 1803 (colloquial do for "ruin, damage" is from 1740). To have done it "to have been very foolish, made a mess of things" is from 1837.