It's a bit hard to give an intuitive reason, but the math is not that complicated (working here in three-dimensional Euclidean space, i.e., "classical vector analysis").
First let's look at a vector field that is the gradient of a scalar field,
\vec{V}=-\vec{\nabla} \phi.
In cartesian coordinates you have
V_j=-\partial_j \phi.
Suppose now that V_j are continuously differentiable wrt. all three coordinates, then you necessarily have
\partial_k V_j-\partial_j V_k=-(\partial_k \partial_j-\partial_j \partial_k) \phi=0,
because under these assumptions the partial derivatives commute. The hodge dual of this antisymmetric tensor is the curl of the vector field, i.e., we have (coordinate independently!)
\vec{\nabla} \times \vec{V}=0.
Here I use, as usual in the physics literature, the symbol "0" for both scalar and vector quantities. There shouldn't be any trouble with this, for mathematicians somewhat sloppy, notation. It's clear from the context, that here we mean the zero vector of Euclidean vector space. I wouldn't like the notation (0,0,0), because that are the components of the zero vector wrt. to a basis but not the coordinate independent zero vector itself.
Now the question is the opposite, i.e., given that for a continuously differentiable vector field
\vec{\nabla} \times \vec{V}=0
holds in some region of space, does there always exist a scalar field such that the vector field is given by the gradient.
The answer is often yes, but not always! It depends on the region of space, where the curl vanishes and where the vector field is well defined. The answer is that in any open region that is simply connected the assertion is correct. Simply connected means that any closed curve within this region can be continuously contracted to a single point within this region.
Then it is easy to show that for any curve \mathcal{C}(\vec{x}_1,\vec{x}), connecting a fixed point \vec{x}_1 with \vec{x} fully contained in that region, the integral
\phi(\vec{x})=-\int_{\mathcal{C}(\vec{x}_1,\vec{x})} \mathrm{d} \vec{y} \cdot \vec{V}(\vec{y})
is independent of the particular choice of the curve. Since the region has been assumed to be open, one can also take the gradient of this field, and it is easy to show that indeed
\vec{\nabla} \phi=-\vec{V}.
There's another theorem of this kind. If for a continuously differentiable vector field \vec{\nabla} \cdot \vec{V}=0 in a simply connected open region, then there exists a vector potential \vec{A}, such that
\vec{V}=\vec{\nabla} \times \vec{A}
in this region.
These are special cases of Poincare's lemma, specialized to three-dimensional space. You find the proof in any textbook on vector calculus (I know only German ones, so that I can't give a particular reference).
Then there is Helmholtz decomposition theorem, stating that any "sufficiently nice" vector field can be decomposed into a gradient and a vector field. The former contains all sources and the second all vortices of the field. I.e. there is always a scalar and a vector potential such that
\vec{V}=-\vec{\nabla} \phi+\vec{\nabla} \times \vec{A}.
