1650s, "in an outdated style, formed in a fashion that has become obsolete," from old + past participle of fashion (v.). Meaning "partaking of the old ways, suited to the tastes of former times" is from 1680s. Related: Old-fashionedness. New-fashioned is recorded from 1610s.
As a type of cocktail, Old Fashioned is attested by 1901, American English, short for a fuller name.
Old Fashioned Tom Gin Cocktail Mix same as Holland Gin Old Fashioned Cocktail using Old Tom gin in place of Holland [George J. Kappeler, "Modern American Drinks," Akron, Ohio, 1900]
(Old Tom (1821) was a name for a strong variety of English gin.)