In this article, we introduce and study a novel class of graphs called power congruence graphs (PCGs) that are constructed over the sets of moduli of the form $M_p=\{p^t:t\ge 1,p^t<n\}$, where $p$ is a prime. For $n\in {\mathbb{Z}}^{+}$, consider $V=\{0,1,\dots ,n-1\}$ as the vertex set. We construct a simple, undirected graph $G(n,k,M_p)$ without loops or multiple edges over $V$ in which two distinct vertices $a,b\in V$ are adjacent if $a^k\equiv b(\text{mod}m)$ for some $m\in M_p$ and fixed $k\in {\mathbb{Z}}^{+}$. We present a comprehensive structural characterization of PGCs for the cases $p=2,3,5$ and extend the framework to an arbitrary prime $p$. When $p=2$, the graph decomposes into two disjoint complete components for all $k$. When $p=3$, the graph structure is governed by $k\text{mod}2$; for odd value of $k$, the graph is a disjoint union of three complete components; and for even value of $k$, the graph is a disjoint union of one complete component and one component $K_n^F$ obtained from a complete graph $K_n$ by deleting a specified set of edges $F\subseteq E(K_n)$. When $p=5$, the graph becomes more intricate and depends on $k\text{mod}4$, producing configurations that include both complete components and components $K_n^F$ obtained from a complete graph $K_n$ by deleting a specified set of edges $F\subseteq E(K_n)$. In general, for a prime $p$, the structure of the graph is determined by the residue class of $k\text{mod}(p-1)$, giving rise to up to $p-1$ distinct structural types. This highlights a systematic transition from simple to increasingly complex graph configurations as the prime modulus increases. Furthermore, we investigate several graph invariants associated with these graphs. This study provides a framework for understanding power congruence-based graph constructions bridging number theory with graph theory.