  We prove a skew generalization of the Newton-Puiseux theorem for the field $F
= \bigcup_{n=1}^\infty \mathbb{C}((x^\frac{1}{n}))$ of Puiseux series: For any
positive real number $\alpha$, we consider the $\mathbb{C}$-automorphism
$\sigma$ of $F$ given by $x \mapsto \alpha x$, and prove that every
non-constant polynomial in the skew polynomial ring $F[t,\sigma]$ factors into
a product of linear terms. This generalizes the classical theorem where $\sigma
= {\rm id}$, and gives the first concrete example of a field of characteristic
$0$ that is algebraically closed with respect to a non-trivial automorphism --
a notion studied in works of Aryapoor and of Smith. Our result also resolves an
open question of Aryapoor concerning such fields. A key ingredient in the proof
is a new variant of Hensel's lemma.
