I develop a method for making automatic velocity picks from velocity semblance scans, using a Monte Carlo nonlinear fitting technique. Given a single velocity semblance scan, random interval velocity models are generated by performing many Monte Carlo random walks. For each trial random interval velocity model, the corresponding rms velocity is calculated, and the semblance is integrated along the trial rms velocity path through the velocity scan. After several random walks, one interval velocity model, and its associated rms velocity function, is retained as the global best fit to the velocity scan which maximizes semblance. The result is a nonlinearly optimal rms velocity function, and an associated geologically reasonable interval velocity model, at each surface CMP location. I tested the method on 300 marine CMP gathers, and the Monte Carlo picks gave reasonable rms and interval velocity models which enhanced the stacked and prestack migrated images.