For the Fibonacci numbers $F_n$, we have the self-convolution formula $5 \sum_{i=0}^n F_i F_{n-i} = (2n)F_{n+1} - (n+1)F_n$. We find the corresponding self-convolution formula for the Narayana numbers $R_n$ which satisfy $R_n = R_{n-1} + R_{n-3}$, and then generalize it to the $k$-step Narayana numbers $\mathcal{R}_n$ with order-$k$ recurrence formula $\mathcal{R}_n = \mathcal{R}_{n-1} + \mathcal{R}_{n-k}$.