Accuracy of automatic cancer diagnosis is largely determined by two factors, namely, the precision of tumor segmentation, and the suitability of extracted features for discrimination between malignancy and benignancy. In this paper, we propose a new framework for accurate characterization of tumors in contrast enhanced MR images. First, a new graph cut based segmentation algorithm is developed for refining coarse manual segmentation, which allows precise identification of tumor regions. Second, by considering serial contrast-enhanced images as a single spatio-temporal image, a spatio-temporal model of segmented tumor is constructed to extract Spatio-Temporal Enhancement Patterns (STEPs). STEPs are designed to capture not only dynamic enhancement and architectural features, but also spatial variations of pixel-wise temporal enhancement of the tumor. While temporal enhancement features are extracted through Fourier transform, the resulting STEP framework captures spatial patterns of temporal enhancement features via moment invariants and rotation invariant Gabor textures. High accuracy of the proposed framework is a direct consequence of this two pronged approach, which is validated through experiments yielding, for instance, an area of 0.97 under the ROC curve.