Background: A growing number of Coronavirus Disease-2019 (COVID-19) survivors are affected by post-acute sequelae of SARS CoV-2 infection (PACS). Using electronic health record data, we aimed to characterize PASC-associated diagnoses and develop risk prediction models. Methods: In our cohort of 63,675 patients with a history of COVID-19, 1724 (2.7%) had a recorded PASC diagnosis. We used a case–control study design and phenome-wide scans to characterize PASC-associated phenotypes of the pre-, acute-, and post-COVID-19 periods. We also integrated PASC-associated phenotypes into phenotype risk scores (PheRSs) and evaluated their predictive performance. Results: In the post-COVID-19 period, known PASC symptoms (e.g., shortness of breath, malaise/fatigue) and musculoskeletal, infectious, and digestive disorders were enriched among PASC cases. We found seven phenotypes in the pre-COVID-19 period (e.g., irritable bowel syndrome, concussion, nausea/vomiting) and sixty-nine phenotypes in the acute-COVID-19 period (predominantly respiratory, circulatory, neurological) associated with PASC. The derived pre- and acute-COVID-19 PheRSs stratified risk well, e.g., the combined PheRSs identified a quarter of the cohort with a history of COVID-19 with a 3.5-fold increased risk (95% CI: 2.19, 5.55) for PASC compared to the bottom 50%. Conclusions: The uncovered PASC-associated diagnoses across categories highlighted a complex arrangement of presenting and likely predisposing features, some with potential for risk stratification approaches.