Direct imaging surveys for exoplanets commonly exclude binary stars from their target lists, leaving a large part of the overall planet demography unexplored. To address this gap in our understanding of planet formation and evolution, we have launched the first direct imaging survey dedicated to circumbinary planets: SPOTS, the Search for Planets Orbiting Two Stars. In this paper, we discuss the theoretical context, scientific merit, and technical feasibility of such observations, describe the target sample and observational strategy of our survey, and report on the first results from our pilot survey of 26 targets with the VLT NaCo facility. While we have not found any confirmed substellar companions to date, a number of promising candidate companions remain to be tested for common proper motion in upcoming follow-up observations. We also report on the astrometry of the three resolved binaries in our target sample. This pilot survey constitutes a successful proof of concept for our survey strategy and paves the way for a second stage of exploratory observations with VLT SPHERE.