This study aims to identify employee perceptions of perceived fairness in performance appraisal system and work performance as the performance appraisal system is crucial to evaluate employees’ performance in every organization; public or private. A private Oil & Gas company in Miri, Sarawak was chosen for this study. Quantitative research method was employed in this study, and closed-ended questionnaires were used to collect data from respondents. Statistical analysis using One Way ANOVA, Pearson correlation, and Independent sample t-test were used to test the hypotheses. The findings showed that there were no significance differences between the selected demographic factors (age, gender, duration of service, highest educational level, and rank) in performance appraisal system and the work performance. Also, there was a significant relationship between the rating accuracy in the performance appraisal system and work performance. Besides that, there was a significant relationship between employee perceptions of leadership styles in decision making in the performance appraisal system and work performance. The findings also showed that employees are concerned with the evaluation and rating given by their supervisor because the outcomes of the performance appraisal will influence their career development in the organization. Thus, performance appraisal system is crucial in increasing the work performance of employees and organization. Organizations should emphasize the role of the performance appraisal system practiced in their organizations and recognize that it is important in improving employees’ performance. Future researchers are encouraged to explore further on the performance appraisal elements that have not been investigated in this study, and conduct the research with a bigger population and sample size.