Classifications of symmetry-protected topological (SPT) phases provide a framework to systematically understand the physical properties and potential applications of topological systems. While such classifications have been widely explored in the context of Hermitian systems, a complete understanding of the roles of more general non-Hermitian symmetries and their associated classification is still lacking. Here, we derive a periodic table for non-interacting SPTs with general non-Hermitian symmetries. Our analysis reveals novel non-Hermitian topological classes, while also naturally incorporating the entire classification of Hermitian systems as a special case of our scheme. Building on top of these results, we derive two independent generalizations of Kramers theorem to the non-Hermitian setting, which constrain the spectra of the system and lead to new topological invariants. To elucidate the physics behind the periodic table, we provide explicit examples of novel non-Hermitian topological invariants, focusing on the symmetry classes in zero, one and two dimensions with new topological classifications (e.g. $mathbb{Z}$ in 0D, $mathbb{Z}_2$ in 1D, 2D). These results thus provide a framework for the design and engineering of non-Hermitian symmetry-protected topological systems.