Let \(\mathscr {C}_\mathbb {Z}([0,1])\) be the metric space of real-valued continuous functions on [0, 1] with integer values at 0 and 1, equipped with the uniform (supremum) metric \(d_\infty \) . It is a classical theorem in approximation theory that the ring \(\mathbb {Z}[X]\) of polynomials with integer coefficients, when considered as a set of functions on [0, 1], is dense in \(\mathscr {C}_\mathbb {Z}([0,1])\) . In this paper, we offer a strengthening of this result by identifying a substantially small subset \(\bigcup _n \mathscr {B}_n\) of \(\mathbb {Z}[X]\) which is still dense in \(\mathscr {C}_\mathbb {Z}([0,1])\) . Here \(\mathscr {B}_n\) , which we call the “Bernstein lattice,” is the lattice generated by the polynomials \( p_{n,k}(x) := \left( {\begin{array}{c}n\\ k\end{array}}\right) x^k(1-x)^{n-k}, ~~k=0,\dots ,n. \) Quantitatively, we show that for any \(f \in \mathscr {C}_\mathbb {Z}([0,1])\) , \( d_\infty (f, \mathscr {B}_n) \le \frac{9}{4} \omega _f(n^{-1/3}) + 2 n^{-1/3}, ~~n \ge 1, \) where \(\omega _f\) stands for the modulus of continuity of f. We also offer a more general bound which can be optimized to yield better decay of approximation error for specific classes of continuous functions.