We examined the structure of intra- and postoperative case-collaboration networks among the surgical service providers in a quaternary-care academic medical center, using retrospective electronic medical record (EMR) data. We also analyzed the evolution of the network properties over time, as changes in nodes and edges can affect the network structure. We used de-identified intra- and postoperative data for adult patients, ages ≥ 21, who received nonambulatory/nonobstetric surgery at Shands at the University of Florida between June 1, 2011 and November 1, 2014. The intraoperative segment contained 30,245 surgical cases, and the postoperative segment considered 30,202 hospitalizations. Our results confirmed the existence of small-world structure in both intra- and postoperative surgical team networks. In addition, high network density was observed in the intraoperative segment and partially in postoperative one, representing the existence of cohesive clusters of providers. We also observed that the small-world property is exhibited more in the intraoperative compared to the postoperative network. Analyzing the temporal aspects of the networks revealed that the postoperative segment tends to lose its cohesiveness as time passes. Finally, we observed the small-world structure is negatively related to patients’ outcome in both intra- and postoperative networks whereas the relation between the outcome and network density is positive. Small changes in graph-theoretic properties of the intra- and postoperative networks cause changes in the intensity of the structural properties. However, due to the special characteristics of the examined networks (e.g., high interconnectivity, team oriented), the network is less likely to lose its structural properties unless the central hubs are removed. Our results highlight the importance of stability of personnel in key positions. This highlights the important role of the central players in the network that offers change leaders the opportunity to quantify and target those nodes as mediators of process change.