Working memory impairment is a common affliction in disorders such as Alzheimer’s disease, attention-deficit hyperactivity disorder (ADHD), and major depression, among others. Brain stimulation is a promising tool for modulating brain networks and improving cognitive performance. We applied non-invasive brain stimulation—using transcranial magnetic stimulation (TMS)—in a real-time brain state-dependent manner to frontal and parietal regions of the brain that are involved in working memory with the goal of memory enhancement in healthy subjects. Theta oscillation phase was used as a brain state marker and change in accuracy rate in a working memory task serve as an outcome measure. This fully non-invasive protocol employs real-time analysis of electrophysiologic signals from the brain using EEG to trigger TMS pulses at specific phases of the ongoing theta oscillation. We found that applying paired magnetic pulses specifically during the theta oscillation positive peak significantly enhances working memory accuracy compared to baseline. There was no significant change in accuracy using the brain state uncoupled protocol. Targeting the pathway specific to a memory network may maximize the cognitive enhancement potential of brain state-dependent cortical paired associative stimulation (cPAS) in healthy individuals and patients with Alzheimer’s disease, ADHD, depression, and other disorders affecting memory.