Real world datasets often contain outliers, and the presence of outliers can make the clustering problems to be much more challenging. Existing algorithms that are specifically designed to handle clustering with outliers often suffer from high computational complexities, rendering them impractical for large-scale applications which is a common scenario in the era of big data. In this paper, we propose a simple yet effective sublinear framework for solving two representative center-based clustering with outliers problems: k-median and k-means clustering with outliers. Our analysis is fundamentally different from the previous (uniform and non-uniform) sampling based ideas. In particular, our sample complexity is independent of the input size and dimensionality, and thus it is suitable for dealing with large-scale and high-dimensional datasets. To further enhance the success probability, we repeat the algorithm multiple times and select a suitable result in sub-linear time. To validate the efficacy of our proposed framework, we also conduct a set of experiments to evaluate the effectiveness of our proposed method on both synthetic and real datasets.