Context. Open clusters (OCs) are popular tracers of the structure and evolutionary history of the Galactic disc. 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. Aims. We perform a systematic search for new OCs in the direction of Perseus using precise and accurate astrometry from Gaia DR2. Methods. We implemented a coarse-to-fine search method. First, we exploited 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 employed a Gaussian mixture model in the proper motion space to tag fields quickly around OC candidates. Thirdly, we applied an unsupervised membership assignment method, UPMASK, to scrutinise the candidates. We visually inspected colour-magnitude diagrams to validate the detected objects. Finally, we performed a diagnostic to quantify the significance of each identified over-density in proper motion and in parallax space. Results. 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 study challenges the previous claim of a near-complete sample of OCs up to 1.8 kpc. Our results reveal that this claim requires revision, and a complete census of nearby OCs is yet to be found.