To enhance expressiveness of forelimb movement and improve the four-beat rhythm of the tölt, Icelandic horses are commonly ridden with excessively high and long hooves. The aim of this study was to objectively assess the effect of shoeing on intra- and inter-limb coordination and limb movement consistency (inter-stride variability) at walk, tölt and trot. Thirteen sound and fit Icelandic horses accustomed to exercise with a rider on a treadmill were assessed with long and high hooves commonly used for competition (SH) and with the hooves trimmed according to the standards of normal shoeing (SN). Limb timing variables were extracted from the four vertical ground reaction force curves measured with an instrumented treadmill. Measurements were taken at walk and at two tölting and trotting speeds. High hooves with long toes reduced stride rate and increased breakover duration. At the tölt, the footfall rhythm showed less tendency to lateral couplets. Movement consistency of the walk remained unchanged, whereas, at the tölt, stride-to-stride variability of selected time parameters increased in SH and/or at the higher velocity. At the faster trotting speed, variability of hind limb duty factor decreased, whereas variability of contralateral step duration in the forelimb increased. High hooves with long toes improve the clearness of the four-beat footfall rhythm of the tölt, but disturb the movement consistency of the gait. The prolonged breakover duration observed in all gaits may have negative implications for the health of the palmar structures of the distal foot.