We study natural $*$-valuations, $*$-places and graded $*$-rings associated with $*$-ordered rings. We prove that the natural $*$-valuation is always quasi-Ore and is even quasi-commutative (\emph{i.e.,} the corresponding graded $*$-ring is commutative), provided the ring contains an imaginary unit. Furthermore, it is proved that the graded $*$-ring is isomorphic to a twisted semigroup algebra. Our results are applied to answer a question of Cimpri\v c regarding $*$-orderability of quantum groups.