Open clusters (OCs) are popular tracers of the structure and evolutionary history of the Galactic disk. The OC population is often considered to be complete within 1.8 kpc of the Sun. The recent Gaia Data Release 2 (DR2) allows the latter claim to be challenged. We perform a systematic search for new OCs in the direction of Perseus using precise and accurate astrometry from Gaia DR2. We implement a coarse-to-fine search method. First, we exploit spatial proximity using a fast density-aware partitioning of the sky via a k-d tree in the spatial domain of Galactic coordinates, (l, b). Secondly, we employ a Gaussian mixture model in the proper motion space to quickly tag fields around OC candidates. Thirdly, we apply an unsupervised membership assignment method, UPMASK, to scrutinise the candidates. We visually inspect colour-magnitude diagrams to validate the detected objects. Finally, we perform a diagnostic to quantify the significance of each identified overdensity in proper motion and in parallax space We report the discovery of 41 new stellar clusters. This represents an increment of at least 20% of the previously known OC population in this volume of the Milky Way. We also report on the clear identification of NGC 886, an object previously considered an asterism. This letter challenges the previous claim of a near-complete sample of open clusters up to 1.8 kpc. Our results reveal that this claim requires revision, and a complete census of nearby open clusters is yet to be found.