Traffic congestion is a major factor to consider in the development of a sustainable urban road network. In the past, several mechanisms have been developed to predict congestion, but few have considered an adaptive real-time congestion prediction. This paper proposes two congestion prediction approaches are created. The approaches choose between five different prediction algorithms using the Root Mean Square Error model selection criterion. The implementation consisted of a Global Positioning System based transmitter connected to an Arduino board with a Global System for Mobile/General Packet Radio Service shield that relays the vehicle’s position to a cloud server. A control station then accesses the vehicle’s position in real-time, computes its speed. Based on the calculated speed, it estimates the congestion level and it applies the prediction algorithms to the congestion level to predict the congestion for future time intervals. The performance of the prediction algorithms was analysed, and it was observed that the proposed schemes provide the best prediction results with a lower Mean Square Error than all other prediction algorithms when compared with the actual traffic congestion states.