The detection of surrounding vehicles is an essential task in autonomous driving, which has been drawing enormous attention recently. When using laser scanners, L-Shape fitting is a key step for model-based vehicle detection and tracking, which requires thorough investigation and comprehensive research. In this paper, we formulate the L-Shape fitting as an optimization problem. An efficient search based method is then proposed to find the optimal solution. Our method does not rely on laser scan sequence information and therefore supports convenient data fusion from multiple laser scanners; it is efficient and involves very few parameters for tuning; the approach is also flexible to suit various fitting demands with different fitting criteria. On-road experiments with production-grade laser scanners have demonstrated the effectiveness and robustness of our approach.