We present a new tomography method based on the local beam semblance and the very fast simulated annealing (VFSA) global optimization method. The data space is the local beam semblance calculated using local slant stacks for overlapping offset windows, i.e. beam windows, of the original common-shot or common-receiver gathers. On each beam semblance panel, the first coherency peak can be identified with a particular ray parameter, first-arrival traveltime and beam center position. The forward problem can be solved with any ray tracer to find arrivals matching the identified peaks. Our inversion scheme uses VFSA to find the maximum-a-posteriori (MAP) solution and estimates the uncertainty by applying Bayesian analysis of all the sampled models for a specified model parameterization. This integration of automatic local semblance evaluation instead of first-arrival picking and a fast forward modeling method combined with VFSA to determine the optimal model makes our method robust, efficient and accurate.