Provided are a network-based robot control system and a robot velocity control method in the network-based robot control system. A client calculates a robot control velocity according to its reception state of video data frames captured by a robot, generates a robot control message including the calculated robot control velocity, and transmits the robot control message to the robot. The robot then changes its velocity according to the robot control velocity included in the received robot control message. In this way, the velocity of the robot is controlled according to the video data reception state of the client, thereby allowing a user to easily control the robot regardless of the performance of the client.