It does not rely on EVs, only on IVs. A pokémon's IVs are set in stone; if you don't like your Starmie's IVs, catch another Starmie. EVs gradually increase as you train the pokémon.
Because Hidden Power depends solely on IVs, a given pokémon's type and power of Hidden Power will never change, not even if you evolve it; but they can be very different for a different member of the same species.