Understanding the structural evolution process after the yielding of networks in polymer nanocomposites can provide significant insights into the design and fabrication of high-performance nanocomposites. In this work, using hydroxyl-terminated 1,4-polybutadiene (HTPB)/organo-clay nanocomposite gel as a model, we explored the yielding and recovery process of a polymer network. Linear rheology results revealed the formation of a nanocomposite gel with a house-of-cards structure due to the fully exfoliated 6 to 8 wt% organo-clays. Within this range, nonlinear rheologic experiments were introduced to yield the gel network, and the corresponding recovery processes were monitored. It was found that the main driving force of network reconstruction was the polymer-clay interaction, and the rotation of clay sheets played an important role in arousing stress overshoots. By proton double-quantum (H-1 DQ) NMR spectroscopy, residual dipolar coupling and its distribution contributed by HTPB segments anchored on clay sheets were extracted to unveil the physical network information. During the yielding process of a house-of-cards network, e.g., 8 wt% organo-clay, nearly one-fourth of physical cross-linking was broken. Based on the rheology and H-1 DQ NMR results, a tentative model was proposed to illustrate the yielding and recovery of the network in HTPB/organo-clay nanocomposite gel.