In this work, we present a combined approach comprising of crystallochemical methods such as Voronoi-Dirichlet partition (VDP), bond valence sums mapping (BVSM) and bond valence energy landscapes (BVEL) for the search for Na-ion cathode materials. Using this approach a systematic screening of the inorganic crystal structure database (ICSD-2016/2) was performed to extract potential cathode materials for Na-ion batteries. As a result, a down-selected and reviewed list of known and newly discovered cathode materials compared and characterized structurally with a special focus on Na+ mobility properties revealed by crystallochemical methods is given. DFT calculations were also carried out for a number of materials to validate the screening algorithm, applicability and reliability of the crystallochemical approaches as well as to get a deeper insight on the Na+ diffusion properties.