Gait recognition has attracted growing attention in recent years as the gait of humans has a strong discriminative ability even under low resolution at a distance. Unfortunately, the performance of gait recognition can be largely affected by view change. To address this problem, we propose a Coupled Patch Alignment (CPA) algorithm that effectively matches a pair of gaits across different views. To realize CPA, we first build a certain amount of patches, and each of them is made up of a sample as well as its intra-class and inter-class nearest-neighbors. Then we design an objective function for each patch to balance the cross-view intra-class compactness and the cross-view inter-class separability. Finally, all the local independent patches are combined to render a unified objective function. Theoretically, we show that the proposed CPA has a close relationship with Canonical Correlation Analysis (CCA). Algorithmically, we extend CPA to "Multi-dimensional Patch Alignment" (MPA) that can handle an arbitrary number of views. Comprehensive experiments on CASIA(B), USF and OU-ISIR gait databases firmly demonstrate the effectiveness of our methods over other existing popular methods in terms of cross-view gait recognition.