This is not actually a constraint on $\mathbf{A}$, rather a way of calculating the electric field from it.
Maxwell's equations are
\begin{align}
\begin{gathered}
\nabla\cdot\mathbf{E}=\frac{\rho}{\epsilon_0} &\qquad \nabla\cdot\mathbf{B}=0\\
\nabla\times\mathbf{E}=-\frac{\partial\mathbf{B}}{\partial t} &\qquad \nabla\times\mathbf{B}=\mu_0\mathbf{J}+\mu_0\epsilon_0\frac{\partial\mathbf{E}}{\partial t}
\end{gathered}
\end{align}
As you said, $\nabla\cdot\mathbf{B}=0$ implies that there exists some vector potential $\mathbf{A}$ which satisfies $\mathbf{B} = \nabla\times\mathbf{A}$. This is the only condition which $\mathbf{A}$ must satisfy.
Replacing $\mathbf{B}$ with $\nabla\times\mathbf{A}$ in the third equation gives
$$
\nabla\times\mathbf{E}=-\frac{\partial}{\partial t}(\nabla\times\mathbf{A}) = -\nabla\times\left(\frac{\partial \mathbf{A}}{\partial t}\right)
$$
so that
$$
\nabla\times\left(\mathbf{E}+\frac{\partial \mathbf{A}}{\partial t}\right) =\mathbf{0}.
$$
This means that $\mathbf{E}+\frac{\partial \mathbf{A}}{\partial t}$ may be written as the gradient of some scalar field $\phi$, i.e.
$$
\mathbf{E}+\frac{\partial \mathbf{A}}{\partial t} = -\nabla\phi.
$$
This potential formulation is extremely useful and turns out to be very fundamental.
