Genetic circuits perform computational operations based on interactions between freely diffusing molecules within a cell. When transcription factors are combined to build a circuit, unintended interactions can disrupt its function. Here, we apply “part mining” to build a library of 73 TetR-family repressors gleaned from prokaryotic genomes. The operators of a subset were determined using an in vitro method and this information was used to build synthetic promoters. The promoters and repressors were screened for cross-reactions. Of these, 16 were identified that both strongly repress their cognate promoter (5- to 207-fold) and do not interact with other promoters. Each repressor:promoter pair was converted to a NOT gate and characterized. Used as a set of 16 NOR gates, there are >10 54 circuits that could be built by changing the pattern of input and output promoters. This represents a large set of compatible gates that can be used to construct user-defined circuits.