In this paper, a novel manifold learning algorithm for face recognition and gender classification – orthogonal nearest neighbour feature line embedding (ONNFLE) – is proposed. Three of the drawbacks of the nearest feature space embedding (NFSE) method are solved: the extrapolation/interpolation error, high computational load and non-orthogonal eigenvector problems. The extrapolation error occurs if the distance from a specified point to one line is small when that line passes through two farther points. The scatter matrix generated by the invalid discriminant vectors does not efficiently preserve the locally topological structure – incorrect selection reduces recognition. To remedy this, the nearest neighbour (NN) selection strategy was used in the proposed method. In addition, the high computational load was reduced using a selection strategy. The last problem involved solving the non-orthogonal eigenvectors found with the NFSE algorithm. The proposed algorithm generated orthogonal bases possessing more discriminating power. Experiments were conducted to demonstrate the effectiveness of the proposed algorithm.