Recruitment of cofactors to specific DNA sites is integral for specificity in gene regulation. As a model system, we examined how targeting and transcriptional control of the sulfur metabolism genes in Saccharomyces cerevisiae is governed by recruitment of the transcriptional co-activator Met4. We developed genome-scale approaches to measure transcription factor (TF) DNA-binding affinities and cofactor recruitment to >1300 genomic binding site sequences. We report that genes responding to the TF Cbf1 and cofactor Met28 contain a novel 'recruitment motif' (RYAAT), adjacent to Cbf1 binding sites, which enhances the binding of a Met4-Met28-Cbf1 regulatory complex, and that abrogation of this motif significantly reduces gene induction under low-sulfur conditions. Furthermore, we show that correct recognition of this composite motif requires both non-DNA-binding cofactors Met4 and Met28. Finally, we demonstrate that the presence of an RYAAT motif next to a Cbf1 site, rather than Cbf1 binding affinity, specifies Cbf1-dependent sulfur metabolism genes. Our results highlight the need to examine TF/cofactor complexes, as novel specificity can result from cofactors that lack intrinsic DNA-binding specificity.