An apparatus and a method for controlling a velocity of an autonomous driving vehicle is provided. The method includes steps of: obtaining information of an environment surrounding the vehicle when an obstacle is detected to be on a planning path of the vehicle; obtaining an initial reference velocity profile of the vehicle; determining a safety factor based on the initial reference velocity profile, the information of the environment and information of the vehicle, wherein the safety factor at least comprises a safety distance between the vehicle and the obstacle for the vehicle to follow the obstacle; determining an optimized reference velocity profile based on the information of the environment, the information of the vehicle and the safety factor; and performing the step of determining the safety factor by using the optimized reference velocity profile as the initial reference velocity profile and the step of determining the optimized reference velocity iteratively.