The generalization of high speed Internet, efficient compression techniques and low cost hardware have resulted in low cost video communication since the year 2000. For the Deaf community, this enables native communication in sign language and a better communication with hearing people over the phone. This implies that Video Relay Service can take over the old Text Relay Service which is less natural and requires mastering written language. A number of such services have developed throughout the world. The objectives of this paper are to present the experience gained in the Walloon Region of Belgium, to share a number of lessons learnt, and to provide recommendations at the technical, user adoption and political levels. A survey of video relay services around the world is presented together with the feedback from users both before and after using the pilot service.