Currently, the only reliable indicator of malignancy in pheochromocytoma is the presence of distant metastasis or extensive local invasion; predicting behavior of pheochromocytoma remains challenging. We aimed to correlate the behavior of pheochromocytoma with its expression of nm-23, cyclooxygenase (COX)-2, and galectin-3 (genes used to predict the course of some neoplastic diseases), evaluated immunohistochemically in 55 paraffin blocks of formalin-fixed pheochromocytoma specimens with confirmed behavior. In 3 (7%) of 44 benign and 7 (64%) of 11 malignant pheochromocytomas, there was negative nm-23 expression (P = .000). COX-2 immunoreactivity was positive in 10 (23%) of benign and 9 (82%) of malignant tumors (P = .000). Galectin-3 was expressed in 5 (11%) of benign and 9 (82%) of malignant pheochromocytomas (P = .000). Negative nm-23, along with positive COX-2 or galectin-3, predicted malignancy with 100% specificity. Dual negativity for galectin-3 and COX-2, along with nm-23 positivity, indicated benign behavior with 100% sensitivity. In early pheochromocytoma, evaluation of nm-23, galectin-3, and COX-2 expression could predict the outcome. Larger studies seem necessary to confirm the potential practical value of our findings.