Cloud computing is an information technology model that provides access to system resources with higher level of services capability. These resources are considered reliable, flexible and affordable for many types of applications and users. Gaming industry is one filed that gained benefits of cloud computing as new cloud gaming architectures have been introduced. Many advantages of cloud gaming have affected the success of gaming according to the improvements on traditional online gaming. However, cloud gaming suffers from several drawbacks such as the huge amount of required video processing and the computational complexity needed. This paper shows the original system drawbacks and devises a new and novel algorithm for speeding up the encoding process and reducing the computational complexity. Improvements on the video codec led to 41% speeding up on the total encoding time with negligible loss of users’ satisfactions.