Three-dimensional waveform inversion is significantly constrained by modern computers’ memory size and hard disk access speed. The limitation arises during the gradient calculation steps, in which, in using conventional algorithms, at least one 4D wavefield volume needs to be saved for the calculation. Random boundary conditions (BCs) can be used to avoid the need for saving the 4D wavefield. However, the lower frequency data used in waveform inversion (WI) make the original random boundary designed for reverse time migration (RTM) less effective, leading to undesired artifacts in the gradient. Although increase in boundary size can mitigate this problem, the associated extracomputational cost decreases the computational advantage of the random boundary, particularly in 3D. To maintain the computational advantage of a random boundary region that has a similar size to the one used in RTM and yet still effectively scatter the incidental wavefield into the boundary region, we have proposed a new random boundary design for the low-frequency wave propagation used in WI. The proposed random boundary used larger, irregularly shaped zones of randomized velocities that were effective in introducing incoherency in wavefronts at a large range of wavelengths. The WI using the new random BC gave as good results as the one using absorbing BCs. We have determined the effectiveness of the proposed random boundary design using the finite-difference modeling and synthetic WI examples.