The National Heart, Lung, and Blood Institute-funded National MDS Natural History Study (NCT02775383) is a prospective cohort study enrolling patients with cytopenia with suspected myelodysplastic syndromes (MDS) to evaluate factors associated with disease. Here, we sequenced 53 genes in bone marrow samples harvested from 1298 patients diagnosed with myeloid malignancy, including MDS and non-MDS myeloid malignancy or alternative marrow conditions with cytopenia based on concordance between independent histopathologic reviews (local, centralized, and tertiary to adjudicate disagreements when needed). We developed a novel 2-stage diagnostic classifier based on mutational profiles in 18 of 53 sequenced genes that were sufficient to best predict a diagnosis of myeloid malignancy and among those with a predicted myeloid malignancy, predict whether they had MDS. The classifier achieved a positive predictive value (PPV) of 0.84 and negative predictive value (NPV) of 0.8 with an area under the receiver operating characteristic curve (AUROC) of 0.85 when classifying patients as having myeloid vs no myeloid malignancy based on variant allele frequencies (VAFs) in 17 genes and a PPV of 0.71 and NPV of 0.64 with an AUROC of 0.73 when classifying patients as having MDS vs non-MDS malignancy based on VAFs in 10 genes. We next assessed how this approach could complement histopathology to improve diagnostic accuracy. For 99 of 139 (71%) patients (PPV of 0.83 and NPV of 0.65) with local and centralized histopathologic disagreement in myeloid vs no myeloid malignancy, the classifier-predicted diagnosis agreed with the tertiary pathology review (considered the internal gold standard).