Most numerical schemes proposed for solving BGK models for rarefied gas dynamics are based on the discrete velocity approximation. Since such approach uses fixed velocity grids, one must secure a sufficiently large domain with fine velocity grids to resolve the structure of distribution functions. When one treats high Mach number problems, the computational cost becomes prohibitively expensive. In this paper, we propose a velocity adaptation technique in the semi-Lagrangian framework for BGK model. The velocity grid will be set locally in time and space, according to mean velocity and temperature. We apply a weighted minimization approach to impose conservation. We presented several numerical tests that illustrate the effectiveness of our proposed scheme.