Memory and logic are central to complex state-dependent computing, and state-dependent behaviors are a feature of natural biological systems. Recently, we created a platform for integrated logic and memory by using synthetic gene circuits, and we demonstrated the implementation of all two-input logic gates with memory in living cells. Here we provide a detailed protocol for the construction of two-input Boolean logic functions with concomitant DNA-based memory. This technology platform allows for straightforward assembly of integrated logic-and-memory circuits that implement desired behaviors within a couple of weeks. It should enable the encoding of advanced computational operations in living cells, including sequential-logic and biological-state machines, for a broad range of applications in biotechnology, basic science and biosensing.