Cardiac allograft rejection is currently diagnosed from endomyocardial biopsies (EMB) that are invasive and impractical to repeat. A serological marker could facilitate rejection monitoring and minimize EMB-associated risks. We investigated the relation of serum matrix metalloprotease (MMP)-1 and vascular endothelial growth factor (VEGF)-A concentrations to cardiac allograft rejection, using 1176 EMBs and serum samples obtained from 208 recipients. Acute cellular rejection was diagnosed in 186 EMBs. Mean week 1 and week 2 serum MMP-1 concentrations predicted rejection (p = 0.001, AUC = 0.80). At the optimal cut-off level of ≥7.5 ng/mL, MMP-1 predicted rejection with 82% sensitivity and 72% specificity. Initial serum MMP-1 <5.3 ng/mL (lowest quartile) was associated with rejection-free outcome in 80% of patients. Both MMP-1 (p < 0.001, AUC = 0.67–0.75) and VEGF-A (p < 0.01, AUC = 0.62–0.67) predicted rejection on the next EMB, while rejection at EMB was identified only by VEGF-A (p < 0.02, AUC = 0.70–0.77). Patients receiving combined cyclosporine-A and everolimus had the lowest serum MMP-1 concentrations. While serum MMP-1 predicts rejection-free outcome and VEGF-A identifies rejection on EMB, both markers predict rejection in follow-up of cardiac transplant recipients. Combination of serum MMP-1 and VEGF-A concentration may be a noninvasive prognostic marker of cardiac allograft rejection, and could have important implications for choice of surveillance and immunosuppression protocols.