This paper presents the design and validation of a novel eddy current (EC) probe that can be used to detect deep sub-surface cracks and characterise the properties of graphite bricks, such as those used to make up the core of an Advanced Gas-cooled Reactor (AGR). In this study, a curved asymmetrical gradiometer probe has been devised and optimised to enhance the depth sensitivity to defects and conductivity variations in the graphite. Experimental and numerical studies are carried out. The results show an average of 43.00% improvement in sensitivity compared to a traditional axial gradiometer routinely used during AGR core inspections. Further experimental tests on a graphite brick containing multiple closed key-way root sub-surface cracks show the superiority of the proposed probe over the traditional probe at locating deep sub-surface cracks that were not detected previously.