Tumors that lack pre-existing immune infiltration respond poorly to T cell checkpoint blockade immunotherapy. These cancers often surround themselves with high densities of suppressive myeloid stroma while excluding immunostimulatory dendritic cells. Tumor-resident myeloid cells and selected lymphocyte populations retain expression of Toll-like Receptors (TLR) that sense common features of pathogens and activate innate immunity in response. We explored whether agonists of TLR9 could augment innate immunity to promote tumor regression alone or in combination with T cell checkpoint blockade. In the setting of the immunogenic B16-Ova (Ovalbumin) expressing melanoma model, local injection of the CpG oligonucleotide TLR9 agonist ODN1826 combined with systemic CTLA-4 blockade cured 45% of mice of both their treated and an untreated tumor on the opposite flank demonstrating the synergistic potential of this combination. Next, in the non-immunogenic B16-F10 melanoma model, we showed that only intra-tumoral, but not systemic TLR9 activation augments the therapeutic potential of checkpoint blockade. In this setting, intra-tumoral TLR9 activation cooperated equally with either CTLA-4 or PD-1 blockade co-administered locally or given systemically; however, the uninjected tumor rarely regressed. Anti-CTLA-4 combinations were associated with improved intra-tumoral CD8 to regulatory T cell ratios, while anti-PD-1 combinations elicited improved ratios of CD8 T cells relative to suppressive myeloid stroma. Using both a TLR9 agonist (MGN1703) and a CTLA-4 antibody (9D9-IgG2a) of increased potency cured 50% of bi-lateral B16-F10 melanoma. These findings suggest that intra-tumoral TLR9 agonists can improve sensitivity of poorly immunogenic tumors to T cell checkpoint blockade, and that newer, higher potency TLR agonists and checkpoint antibodies can raise the therapeutic ceiling for this combination therapy.