Since $p$ is the smallest prime dividing $|G|$, and $|G:H|=p$, we know that $H$ is the largest proper subgroup of $G$. So the normalizer $N_G(H)$ must be equal to either $G$ or $H$.
If $N_G(H)=G$, then $H$ is normal, so we are done. If $N_G(H)=H$, I have to show that it leads to a contradiction.
If we let $G$ act on conjugates of $H$ by conjugation, then the stabilizer of $H$ becomes $N_G(H)$ and it is equal to $H$ so by the orbit-stabilizer theorem we obtain the order of orbit of $H$ must be equal to $p$. This is where I have figured out so far, but don't know how to proceed from here. Any hint would be greatly appreciated.
Let $S = \{ H = g_1 H,g_2 H, \cdots , g_p H \}$ be the set of all left cosets of $G$. Then $G$ acts on $S$ by \begin{equation} g \cdot g_i H := (g g_i) H. \end{equation}
Thin induces a homomorphism of groups $\phi : G \rightarrow S_p$. Let $K = \text{Ker } \phi$. Observe that $K \subseteq H$ and $K$ is normal. Now $| G/K|$ divides $|G|$ and $|G/K|$ divides $|S_p|$. You can now use counting arguments to show that $K = H$.