Most of the characters which first spring to mind - Zorro, The Scarlet Pimpernel - are actually from the early Twentieth Century. (BTW, I found a rather interesting silent serial _Les Vampires_, about a sophisticated gang of thieves who had a "uniform" of black leotard and black fabric mask. One of their number, Irma Vep ("vampire" scrambled, the character played by a rather striking woman) appears to be a precursor of Cat Woman.
The earliest appearance I've found so far is fictional versions of Springheeled Jack. These seem to have begun appearing about a decade after the reports of this character in early Nineteenth Century London. The fictional versions appeared in print and on stage, including in musicals. Often he was portrayed as wearing a distinguishing costume and/or a mask.
Does anyone know of earlier occurrences of this trope?