Cytolytic activity score (CYT), defined by granzyme A and perforin expression, is a useful marker for underlying immunity. We hypothesized that CYT-high hepatocellular carcinomas (HCCs) have stronger immunogenicity and favorable tumor microenvironments, which would result in better clinical outcomes, using the cancer genome atlas (TCGA) cohort with 371 patients with HCC. We found CYT-high HCCs were associated with higher expressions of the apolipoprotein B mRNA editing enzyme catalytic polypeptide-like 3 (APOBEC3), well-known mutagenic enzymes. Further, higher numbers of anti-cancer immune cells, such as CD8+ T cells and M1 macrophages, were infiltrated in CYT-high HCCs. Major T cell exhaustion markers were expressed significantly higher in CYT-high HCCs, likely as a negative feedback loop. Additionally, CYT-high HCCs strongly enriched gene sets related with enhanced immune activity. With strong immunity, patients with CYT-high HCCs had significantly longer disease-specific survival (DSS) and overall survival (OS) ( = 0.03 and <0.01). Furthermore, when the OS is stratified by exhaustion marker expressions, the CYT-high/exhaustion-low group had the best and CYT-low/exhaustion-high groups had the worst OS. Lastly, high CYT was an independent protective factor for prognosis. In conclusion, CYT-high HCCs were associated with enhanced immunity and better survival. Our findings suggest that proper identification of tumor-immune microenvironments could stratify the patients for appropriate treatments.