Pheochromocytoma and paraganglioma (PPGL) are rare tumors that occur in the adrenal medulla and extra-adrenal tissues, respectively. The prognosis and tumor microenvironment (TME) of pseudohypoxic PPGL as a major entity have not been fully described. Based on the clinical database of 65 patients with PPGL, we assessed the morphological features as well as the immunohistochemistry of pseudohypoxia-related proteins (SDHB and CAIX) and TME-related immune cell markers. Furthermore, we compared the relapse-free survival (RFS) rates in localized patients between the pathological subgroups. Among 50 available specimens, 84% and 30% of the cases exhibited at least one morphological adverse feature including vascular/capsular invasion and a Ki-67 index > 3%, respectively. The SDHB and CAIX positivity rates were 81% and 51%. Concerning the immune cell markers, the CD163-positive cell numbers were higher in hypoxia-associated PPGL composed of SDHB-negative or CAIX-positive cases than in non-hypoxia PPGL (median 66 vs. 23/mm). Concerning prognosis, RFS rates were significantly lower in cases with Ki-67 indices > 3% and SDHB-negativity than in those with Ki-67 indices ≤ 3% and SDHB-positivity (3-year rate: 64% vs. 100%, P < 0.001; 57% vs. 100%, P = 0.03). In contrast, RFS was comparable between CAIX-positive and CAIX-negative PPGL cases. Our analyses suggested that SDHB-deficient PPGL exhibited a higher incidence of relapse. Furthermore, M2 macrophage infiltration in TME might be crucial in pseudohypoxic PPGL pathogenesis.