Many parts of the healthcare system remain fragmented and outpatient surgical care is no exception. In this study, we develop a coordinated pre‐operative scheduling approach between Anesthesiology and Internal Medicine to optimize patients’ medical conditions prior to surgery. Coordinating these two services has conceptual appeal because any health issues discovered by the anesthesiologist can often be addressed by a general internist. We design a patient‐centered approach that allows the patient to see both providers, if necessary, on a single visit. This problem is modeled as a two‐station stochastic network, where each station (or clinic) may be staffed by multiple parallel providers and patients see the first available provider. To solve the scheduling problem, we formulate an optimization model to maximize the net benefit of scheduling patients. The objective balances benefits against patient waiting time and clinic overtime costs. We develop a scheduling method with a booking limit to create a balanced network schedule. Due to the complexity of this problem, the solution approach is myopic. In addition, we develop a hybrid method that combines analytical calculation and simulation‐based optimization. We demonstrate our approach on a healthcare network at The University of Texas Health Sciences Center in San Antonio. We compare our method against other policies and show that it yields high quality and robust results. Based on the level of generality of our model and results, the insights gained are not limited to the particular application, but can be applied to other patient‐centered models where scheduling coordination can be used.