Modular and orthogonal genetic logic gates are essential for building robust biologically based digital devices to customize cell signalling in synthetic biology. Here we constructed an orthogonal AND gate in Escherichia coli using a novel hetero-regulation module from Pseudomonas syringae. The device comprises two co-activating genes hrpR and hrpS controlled by separate promoter inputs, and a σ54-dependent hrpL promoter driving the output. The hrpL promoter is activated only when both genes are expressed, generating digital-like AND integration behaviour. The AND gate is demonstrated to be modular by applying new regulated promoters to the inputs, and connecting the output to a NOT gate module to produce a combinatorial NAND gate. The circuits were assembled using a parts-based engineering approach of quantitative characterization, modelling, followed by construction and testing. The results show that new genetic logic devices can be engineered predictably from novel native orthogonal biological control elements using quantitatively in-context characterized parts.