Discovering high-energy cathode materials is critical to constructing K-ion batteries for practical applications. Owing to the great success of layered oxides in Li- and Na-ion systems, K layered cathodes have also been investigated in recent years. However, the much larger size of K+ compared to Li or Na introduces strong K+–K+ interaction within the layer, which results in a sloped voltage profile thereby limiting the specific capacity and operating voltage. In contrast, polyanionic materials with a three-dimensional K+ arrangement can effectively mitigate K+–K+ interaction. In this work, ten K polyanionic compounds with theoretical capacity >100 mAh g−1 are screened from the Inorganic Crystal Structure Database as potential cathode materials for K-ion batteries. Among the ten proposed compounds, K2MnP2O7, K2Mn2P2O7F2, K2Fe2P2O7F2, and K6V2(PO4)4 with average voltage <4.5 V are synthesized and evaluated electrochemically. While the re-insertion of K into these compounds is not fully reversible, it may be related to the very high migration barrier that we compute for K ions. In addition, we show the successful synthesis of a series of K3V3−xCrx(PO4)4 (x = 0, 1, 2, 3) compounds. Among these, K3V2Cr(PO4)4 exhibits the largest reversible capacity, as revealed by the in situ investigation. Finally, we find that the redox couples in many of these compounds sit at remarkably high potential, even higher than in equivalent Li compounds, which brings both opportunities and challenges in the future research of K polyanion cathodes.