For any real $beta$ let $H^2_beta$ be the Hardy-Sobolev space on the unit disk $D$. $H^2_beta$ is a reproducing kernel Hilbert space and its reproducing kernel is bounded when $beta>1/2$. In this paper, we study composition operators $C_varphi$ on $H^2_beta$ for $1/2<beta<1$. Our main result is that, for a non-constant analytic function $varphi:DtoD$, the operator $C_{varphi }$ has dense range in $H_{beta }^{2}$ if and only if the polynomials are dense in a certain Dirichlet space of the domain $varphi(D)$. It follows that if the range of $C_{varphi }$ is dense in $H_{beta }^{2}$, then $varphi $ is a weak-star generator of $H^{infty}$. Note that this conclusion is false for the classical Dirichlet space $mathfrak{D}$. We also characterize Fredholm composition operators on $H^{2}_{beta }$.