The predominance of tissues stored worldwide in hospitals and clinical laboratories exist in formalin-fixed paraffin-embedded (FFPE) blocks that are generated by simple and well-established protocols. Although generation of FFPE tissues has facilitated their characterization by such techniques as histopathology, they have proven refractory to biomarker discovery investigations using state-of-the-art MS-based proteomic methodologies. Very recently new methods have been developed that enable proteins extracted from FFPE tissues to be analyzed by MS. This review will highlight and discuss those efforts that have led to this exciting recent progress. Although these developments are quite new, the ability to conduct MS-based proteomic analyses of FFPE tissues opens heretofore intractable clinical samples for discovery-based biomarker research.