An apparatus and method for extracting signature candidates and optimizing a corresponding signature are provided. The apparatus includes a packet separator, a header parser, a traffic information generator, a substring extractor, and a signature candidate extractor. The packet separator separates a packet into a header and a payload. The header information parser parses the header information, and the traffic information generator generates traffic information. The substring extractor measures a frequency of appearing of a substring with a predetermined length in the separated payload for a constant observation period, and extracts a substring having a frequency higher than a predetermined setup value by updating the measured frequency information to a substring frequency table. The signature candidate extractor generates a signature by collecting the extracted substring information and the generated traffic information, updates a signature frequency table, and extracts a signature candidate with reference to information of the signature frequency table.