Telstra have pushed out the Android 4.0.3 ‘Ice Cream Sandwich’ update to their first 4G device, the HTC Velocity 4G. As promised, it is the first HTC phone on Telstra to receive the update — HTC Sensation can’t be too far off — and can now be downloaded over the air, if you haven’t already updated.

With the update you’ll be brought up to the latest version of Android with plenty of new features and (hopefully) speed increases as well. The version of Sense UI is 3.6 which is the ‘lite’ version of Sense UI 4.0 that is made for devices which can’t quite handle Sense UI 4.0. Enjoy!