In persons living with HIV (PWH), non-AIDS-related tumors, including colorectal cancer (CRC), have become major health concerns worldwide since the introduction of highly active antiretroviral therapy. To date, no study has addressed the underlying molecular mechanisms in PWH with CRC. To explore the impact of PWH with CRC, we sequenced total RNA and DNA from individuals with HIV-negative and PWH formalin-fixed paraffin-embedded (FFPE) CRC for transcriptome and genome analyses. We performed RNA and DNA extraction from FFPE samples, library preparation, total RNA sequencing, and whole-genome sequencing. A total of 1,705 genes were found to be differentially expressed genes (DEGs), including 1,121 upregulated DEGs and 584 downregulated DEGs, in PWH compared with HIV-negative CRC. Functional pathway analysis revealed that the DEGs were enriched mainly in infectious and immune diseases and various metabolic processes. The immune infiltration results revealed that the numbers of activated dendritic cells (aDCs), natural killer T cells (NKT cells), and T follicular helper cells (Tfh cells) were greater and that the number of memory B cells was lower in patients with CRC than in PWH. Twelve hub genes involved in interferon-stimulated genes (ISGs)—IFI44, MX1, OAS1, OAS3, BST2, IFIT1, FGF2, EGF, CCL3, CCL4, SHH, and PPARG—are positively related to aDC, NKT, Tfh, and memory B cells. We found highly analogous insertions, deletions, and functional annotations of the detected single nucleotide polymorphisms and indel mutations in PWH and patients with HIV-negative CRC. This study provides new insights into crucial ISGs, immune infiltration, immune variants, and pathways involved in CRC with HIV infection.