Random feature is one successful technique to approximate traditional kernel functions, and the random feature-based fuzzy clustering has been proved to be effective and efficient for handling non-linear data. However, the existing random feature-based fuzzy clustering methods fail to consider the locality information hidden in original input data. From some perspective, the membership obtained by fuzzy clustering can be seen as the encoding results of data. Thus, constraining the relationships between membership degrees to be consistent with that of data is beneficial to improve clustering performance. To this end, we propose a novel random Fourier feature-based fuzzy clustering method (pLRFCM) in this paper. The random Fourier feature is used to approximate Gaussian kernels in this method, and the fuzzy clustering is performed in the feature space. More importantly, the p-Laplacian regularization is conducted on the membership matrix to preserve the local structures of original data into the clustering results, to guarantee good partition of data. The maximum-entropy technique is also utilized to fine-tune the weights of features automatically during the process of clustering, so as to further promote the performance of clustering. In the experiments on four synthetic non-linear datasets and eight real-world datasets, pLRFCM outperforms several classical and state-of-the-art fuzzy clustering methods.