The leaves of plants provide plenty of information for plant recognition. They play a critical role in distinguishing between olive and henna leaves, although they have similar elliptical shapes, sizes, and textures. Distinguishing between henna and olive leaves is essential as they have different effects on human health, economic stability, and the integrity of various industries. These leaves also have different medicinal properties. This paper implements the Histogram of Oriented Gradients (HOG) method to extract unique features that differentiate olive and henna leaves. The extracted features are utilized as an input for a logistic regression classifier. A new dataset consisting of 193 samples—113 for olive leaves and 80 for henna leaves was generated. The experimental results prove that the proposed model achieved an acceptable classification performance, with precision of 94%, recall of 93.8%, F1-score of 93.6%, and accuracy of 93.8% across five validation folds. The logistic regression classifier with HOG feature extraction outperformed Support Vector Machine (SVM), ExtraTrees, Naïve Bayes, and AdaBoost classifiers.