Data privacy is a hard trade-off problem between privacy level and data utility. Anonymization is one of the most commonly used utility-based solutions for preserving data privacy. The existence of outliers in data set decreases data utility in anonymization. Hence, outliers should be managed in the anonymization process. In traditional approaches, outliers are detected after anonymization and they are partially or completely removed from the published data set. However, detection of outliers after anonymization increases computational cost and the removal of the outliers from the data set reduces total utility. In this study, a new outlier record-oriented utility-based privacy-preserving model named as OAN, which reduces the computational cost by detecting outliers before anonymization and increases data utility by using all data, was proposed. It was shown that OAN is an effective solution in terms of computational cost compared to another utility-based model. According to the experimental results, it was observed that the proposed model increased total data utility while preserving the privacy of data.