Let $G$ be a finite group, and $H$ a subgroup of $G$ with $(G:H)=p$, where $p$ is the smallest prime divisor of $|G|$.
The action of $G$ by left multiplication on the cosets of $H$ defines a homomorphism $\varphi:G\to S_p$ where $S_p$ is the symmetric group on $p$ points. Let $K=\ker\varphi$.
If $g\in K$, then $gH=H$; this shows that $K\subset H$. The image of $\varphi$ has order:
(G:K) = (G:H)(H:K) = p(H:K)
This image is a subgroup of $S_p$, which has order $p!$. This shows that $p(H:K)$ divides $p!$, and $(H:K)$ divides $(p-1)!$.
Now, $(H:K) \mid (G:K) \mid |G|$. As the smallest prime divisor of $|G|$ is $p$ and all the prime divisors of $(p-1)!$ are smaller than $p$, we conclude that $(H:K)=1$ and $K=H$. As $K$ is normal in $G$ as the kernel of a homomorphism, this shows that $H\lhd G$.