Aiming at the problem of initial damage and fatigue damage for polymer bonded explosive (PBX), the nonlinear ultrasonic parameters of two kinds of triamino trintrobenzene(TATB)-based PBX cylindrical specimens with different density formed by compression molding and these specimens in the process of compressive fatigue were tested by self-established nonlinear ultrasonic testing device. The nonlinear ultrasonic testing results were verified by fracture surface analysis and computer tomography (CT) testing. Compared with TATB-based PBX specimens with less initial interfacial micro-damage degree, the nonlinear ultrasonic coefficients of the TATB-based PBX specimens with obvious interfacial damage are obviously higher. There is a certain relevance between the nonlinear ultrasonic coefficient and the initial damage degree of TATB-based PBX. When the microscopic crack is nearly generated in the TATB-based PBX, the nonlinear ultrasonic coefficient increases sharply and reaches maximum, revealing that the nonlinear ultrasonic parameters can monitor the fatigue damage developing process. There is a certain difference in fatigue damage rate and developing process for TATB-based PBX specimens with different initial micro-damage degree.