The Waldschmidt constant $${{\,\mathrm{{\widehat{\alpha }}}\,}}(I)$$ α^(I) of a radical ideal *I* in the coordinate ring of $${\mathbb {P}}^N$$ PN measures (asymptotically) the degree of a hypersurface passing through the set defined by *I* in $${\mathbb {P}}^N$$ PN . Nagata’s approach to the 14th Hilbert Problem was based on computing such constant for the set of points in $${\mathbb {P}}^2$$ P2 . Since then, these constants drew much attention, but still there are no methods to compute them (except for trivial cases). Therefore, the research focuses on looking for accurate bounds for $${{\,\mathrm{{\widehat{\alpha }}}\,}}(I)$$ α^(I) . In the paper, we deal with $${{\,\mathrm{{\widehat{\alpha }}}\,}}(s)$$ α^(s) , the Waldschmidt constant for *s* very general lines in $${\mathbb {P}}^3$$ P3 . We prove that $${{\,\mathrm{{\widehat{\alpha }}}\,}}(s) \ge \lfloor \sqrt{2s-1}\rfloor $$ α^(s)≥⌊2s-1⌋ holds for all *s*, whereas the much stronger bound $${{\,\mathrm{{\widehat{\alpha }}}\,}}(s) \ge \lfloor \sqrt{2.5 s}\rfloor $$ α^(s)≥⌊2.5s⌋ holds for all *s* but $$s=4$$ s=4 , 7 and 10. We also provide an algorithm which gives even better bounds for $${{\,\mathrm{{\widehat{\alpha }}}\,}}(s)$$ α^(s) , very close to the known upper bounds, which are conjecturally equal to $${{\,\mathrm{{\widehat{\alpha }}}\,}}(s)$$ α^(s) for *s* large enough.