In this paper, we develop a new formula for hyper-Fibonacci numbers $F_n^{[k]}$, wherein the coefficients (related to Stirling numbers of the first kind) of the polynomial ingredient $p_k(n)$ are determined. As an application we investigate the number of occurrences of positive integers among $F_n^{[k]}$ and determine all the solutions in nonnegative integers $x$ and $y$ to the Diophantine equation $F_x^{[k]}=F_y^{[\ell]}$, where $0\le k