Topoisomerases relieve topological tension in DNA by breaking and rejoining DNA phosphodiester bonds. Type IB topoisomerases such as vaccinia topoisomerase (vTopo) and human topoisomerase I are structurally and mechanistically similar to the tyrosine recombinase family of enzymes, which includes bacteriophage lambda Integrase (Int). Previously, our laboratory identified peptide inhibitors of Int from a synthetic peptide combinatorial library. The most potent of these peptides also inhibit vTopo. Here, we used the same mixture-based screening procedure to identify peptide inhibitors directly against vTopo using a plasmid relaxation assay. The two most potent new peptides identified, WYCRCK and KCCRCK, inhibit plasmid relaxation, DNA cleavage and Holliday junction (HJ) resolution mediated by vTopo. The peptides tested bind double-stranded DNA at high concentrations but do not appear to displace the enzyme from its DNA substrate. WYCRCK binds specifically to HJ and perturbs the central base-pairing. This peptide also accumulates HJ intermediates when it inhibits Int-mediated recombination, whereas KCCRCK does not. Interestingly, WYCRCK shares four amino acids with a peptide identified against Int, WRWYCR. The octapeptide WRWYCRCK, containing amino acids from both hexapeptides, is more potent than either against vTopo. All peptides are less potent against the type IA Escherichia coli topoisomerase I or against restriction endonucleases. Like the Int-inhibitory peptide WRWYCR, WYCRCK binds to HJs, and both inhibit junction resolution by vTopo. Our results suggest that the newly identified WYCRCK and peptide WRWYCR interact with a distorted DNA intermediate arising during vTopo-mediated catalysis, or interfere with specific interactions between vTopo and DNA.