Carbon has many advantages over transitional metal oxide for being an oxygen reduction reaction (ORR) electrocatalyst due to high activity, low cost, excellent electrical conductivity, and high surface area. Nevertheless, its intrinsic instability in oxygen evolution reaction (OER) potential regime (>1.23 V vs. RHE) has largely inhibited the potential for bifunctional ORR and OER applications in reversible electrochemical energy devices. Here, we reported a new class of highly stable carbon nanocomposite bifunctional catalysts consisting of substantial carbon tubes growing from a very thick and dense graphitic substrate, which is derived from an inexpensive dicyandiamide as carbon/nitrogen precursor simultaneously catalyzed by Fe, Co, Ni, and Mn during carbonization. The dense substrate leverages the characteristics of high degree of graphitization carbon derived from Mn; active nitrogen-doped carbon tubes are stemmed from FeCoNi during carbonization process. The bifunctional stability and activity of the carbon nanocomposite catalysts were found greatly dependent on content of Mn. The existences of various metal/metal oxides and effective nitrogen doping was responsible for its high bifunctional activities for the ORR and the OER. The unprecedented stability of the bifunctional catalyst was verified by using various accelerated stress tests up to 60,000 potential cycles (0-1.9 V vs. RHE) at 25^oC and 100-hour life test at constant current density of 10 mA cm^-2 at 60^oC. Instead of degradation, ORR and OER activity was considerably increased during the long-term potential cycling tests, indicating more active sites gradually exposed. The OER current was verified to be a sole outcome of oxygen evolution, rather than carbon or metal oxidations. The remarkable electrochemical stability of this catalyst was primarily attributed to its unique hybrid carbon structures featured with a very high graphitization degree, thick graphitic layers, and abundances of carbon tubes grown from a dense substrate. More importantly, the irreversible formation of β-MnO₂ phase and FeCoNi based metals oxides provide crucial protection roles in enhancing carbon corrosion resistance.