It is challenging for a mobile robot to avoid moving obstacles in dynamic environments. Traditional velocity obstacle methods do not fully consider the obstacles moving with the speeds larger than the maximum speed of the robot. In this paper, a new obstacle avoidance method, named the maximum-speed aware velocity obstacle (MVO) algorithm, is proposed for a mobile robot to avoid one or multiple high-speed obstacles. The proposed algorithm expands the velocity obstacle region into two parts, where one of the parts foresees collisions beyond the time horizon to ensure the feasible solutions of the current and the next control step. In practical applications, the perception capability of the robot is generally limited, and a non-holonomic robot can’t move into any direction due to its kinematic constraints. In this paper, the limited sensing field of view and non-holonomic kinematic constraints of the mobile robot are incorporated into the proposed MVO method. Moreover, continuity, safety, and computational complexity of the MVO approach are analyzed and presented. Extensive simulations and physical experiments are conducted to verify the efficacy of the MVO method, where a quadrotor and a differential-drive robot are used to perform dynamic obstacle avoidance.