Microorganisms are detected in multiple cancer types, including in putatively sterile organs, but it is unclear whether this relates to specific tissue contexts and influences oncogenesis or anti-tumor responses in humans. We developed SAHMI, a framework to analyze host-microbiome interactions using single-cell sequencing data. Interrogating pancreatic ductal adenocarcinomas (PDA), we identified an altered and diverse tumor microbiome that includes known and novel tumor-associated bacteria and fungi. Specific somatic cell-types were enriched with particular microbes whose abundances correlated with select host gene expression and cancer hallmark activities. Nearly all tumor-infiltrating lymphocytes had infection-reactive transcriptional profiles. Pseudotime analysis provided evidence for tumor-microbial co-evolution and identified three tumor subtypes with distinct microbial, molecular, and clinical characteristics. Finally, using multiple independent datasets, a signature of increased intra-tumoral microbial diversity predicted clinical prognosis. Collectively, tumor-microbiome cross-talk appears to modulate tumorigenesis with implications for clinical management.