This paper proposes a novel input-output clustering approach for structure identification of T-S fuzzy neural networks. This approach consists of two phases. Firstly, k-means clustering method is applied to the input data to provide the initial clusters of the input space. Secondly, check whether the sub-clustering is needed for each input cluster by considering the corresponding output variation and then apply the k-means method to further partition those input clusters needed sub-clustering. Applying the above process recursively leads to the structure identification of a T-S fuzzy neural network and then the parameter identification is completed by using the gradient learning algorithm. The experiments by applying the proposed method to several benchmark problems show better performance compared with many existing methods and then verify the effectiveness and usefulness of the proposed method.