In this note, we extend the definition of multiple harmonic sums and apply their stuffle relations to obtain explicit evaluations of the sums $R_n(p,t)=\sum\nolimits_{m=0}^n m^p H_m^t$, where $H_m$ are harmonic numbers. When $t\le 4$ these sums were first studied by Spieß around 1990 and, more recently, by Jin and Sun. Our key step first is to find an explicit formula of a special type of the extended multiple harmonic sums. This also enables us to provide a general structural result of the sums $R_n(p,t)$ for all $t\ge 0$.