Application of DNA molecular markers to traceability of foods is thought to bring new benefit to consumer's protection. Even in a complex matrix such as olive oil, DNA could be traced with PCR markers such as the amplified fragment length polymorphisms (AFLPs). In this work, fluorescent AFLPs were optimized for the characterization of olive oil DNA, to obtain highly reproducible, high-quality fingerprints, testing different parameters: the concentrations of dNTPs and labeled primer, the kind of Taq DNA polymerase and thermal cycler, and the quantity of DNA employed. It was found that correspondence of fingerprinting by comparing results in oils and in plants was close to 70% and that the DNA extraction from olive oil was the limiting step for the reliability of AFLP profiles, due to the complex matrix analyzed.