We introduce and study Brownian motion on spaces of discrete regular curves in Euclidean space equipped with discrete Sobolev-type metrics. It has been established that these spaces of discrete regular curves are geodesically complete if and only if the Sobolev-type metric is of order two or higher. By relying on a general result by Grigor'yan and controlling the volume growth of geodesic balls, we show that all spaces of discrete regular curves that are geodesically complete are also stochastically complete, that is, the associated Brownian motion exists for all times. This provides a rigorous footing for performing data statistics, such as data inference and data imputation, on these spaces. Our result is the first stochastic completeness result in shape analysis that applies to the full shape space of interest. For illustrative purposes, we include simulations for sample paths of Brownian motion on spaces of discrete regular curves. For the space of triangles in the plane modulo rotation, translation and scaling, we further provide heuristics which suggest that this space remains stochastically complete even for Sobolev-type metrics of order zero and one.