Pigeons can learn structured sequences of cued responses and perform them quickly, even when random variability is later introduced into the originally learned sequence, making some cue locations unpredictable.  In order to determine if initial learning shows the same tolerance of spatial variability as steady-state performance, naïve pigeons were trained on random distortions around a structured sequence without having seen the original sequence itself.  Learning was possible, but accommodated less variability than did performance of the same sequence previously learned in an undistorted context.  Analysis of results indicated that performance of a randomly distorted sequence is best when birds are initially trained with little or no variability, and randomness is later introduced in a gradual fashion.