Changes in connectivity between pairs of neurons can serve as a substrate for information storage and for experience-dependent changes in neuronal circuitry. Early in development, synaptic contacts form and break, but how these dynamics influence the connectivity between pairs of neurons is not known. Here we used time-lapse imaging to examine the synaptic interactions between pairs of cultured cortical pyramidal neurons, and found that the axon-dendrite contacts between each neuronal pair were composed of both a relatively stable and a more labile population. Under basal conditions, loss and gain of contacts within this labile population was well balanced and there was little net change in connectivity. Selectively increasing the levels of activated CaMKII in the postsynaptic neuron increased connectivity between pairs of neurons by increasing the rate of gain of new contacts without affecting the probability of contact loss, or the proportion of stable and labile contacts, and this increase required Calcium/calmodulin binding to CaMKII. Our data suggest that activating CaMKII can increase synaptic connectivity through a CaM-dependent increase in contact formation, followed by stabilization of a constant fraction of new contacts.