The Waldschmidt constant αˆ(I) of a radical ideal I in the coordinate ring of PN measures (asymptotically) the degree of a hypersurface passing through the set defined by I in PN. Nagata’s approach to the 14th Hilbert Problem was based on computing such constant for the set of points in 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 αˆ(I). In the paper, we deal with αˆ(s), the Waldschmidt constant for s very general lines in P3. We prove that αˆ(s)≥⌊2s−1−−−−−√⌋ holds for all s, whereas the much stronger bound αˆ(s)≥⌊2.5s−−−−√⌋ holds for all s but s=4, 7 and 10. We also provide an algorithm which gives even better bounds for αˆ(s), very close to the known upper bounds, which are conjecturally equal to αˆ(s) for s large enough.