Object localization is one of the most important stages in license plate recognition application. Object localization searches and segments the region of interest of license plate automatically and eases the subsequent recognition phase where each character of the license plate can be identified accurately. Speeded Up Robust Features (SURF) and Bag-of Words (BoW) feature descriptors are combined and clustered by using K-means clustering to form a novel way of localizing the license plate's region in an image. The proposed work has been tested on Malaysian license plate datasets in both of off-line and on-line modes, where the offline mode denoted by stand-still image test captured in out-door environment, while the online mode denoted by the video and webcam tests. The obtained results showed that the proposed method can achieve up to 90.69%, 90.32% and 98% of accuracy rates for the license plate localization in standstill image, video and webcam tests subsequently. The results also demonstrate that the proposed method is more promising than the standard SURF.