Synthetic lethality has been proposed as a way to leverage the genetic differences found in tumor cells to affect their selective killing. Cohesins, which tether sister chromatids together until anaphase onset, are mutated in a variety of tumor types. The elucidation of synthetic lethal interactions with cohesin mutants therefore identifies potential therapeutic targets. We used a cross-species approach to identify robust negative genetic interactions with cohesin mutants. Utilizing essential and non-essential mutant synthetic genetic arrays in Saccharomyces cerevisiae, we screened genome-wide for genetic interactions with hypomorphic mutations in cohesin genes. A somatic cell proliferation assay in Caenorhabditis elegans demonstrated that the majority of interactions were conserved. Analysis of the interactions found that cohesin mutants require the function of genes that mediate replication fork progression. Conservation of these interactions between replication fork mediators and cohesin in both yeast and C. elegans prompted us to test whether other replication fork mediators not found in the yeast were required for viability in cohesin mutants. PARP1 has roles in the DNA damage response but also in the restart of stalled replication forks. We found that a hypomorphic allele of the C. elegans SMC1 orthologue, him-1(e879), genetically interacted with mutations in the orthologues of PAR metabolism genes resulting in a reduced brood size and somatic cell defects. We then demonstrated that this interaction is conserved in human cells by showing that PARP inhibitors reduce the viability of cultured human cells depleted for cohesin components. This work demonstrates that large-scale genetic interaction screening in yeast can identify clinically relevant genetic interactions and suggests that PARP inhibitors, which are currently undergoing clinical trials as a treatment of homologous recombination-deficient cancers, may be effective in treating cancers that harbor cohesin mutations.