We demonstrate a probe for nearest-neighbor correlations of fermionic quantum gases in optical lattices. It gives access to spin and density configurations of adjacent sites and relies on creating additional doubly occupied sites by perturbative lattice modulation. The measured correlations for different lattice temperatures are in good agreement with an ab initio calculation without any fitting parameters. This probe opens new prospects for studying the approach to magnetically ordered phases.