Machine learning (ML) based biological gender prediction is helpful for several cases including mental health screening and wearable health technology where monitoring health metrics can involve this task to provide personalized health insights. This task can also have a vital importance for several other cases in which the gathered patient information is missing or has inaccurate gender attribute as well as the need to automatically detect this attribute. Hence, this study focuses on predicting gender from electronic health records using ML, unlike the existing research effort that primarily focuses on disease prediction. Experiments conducted on six medical datasets (primarily created for disease detection) show that the Gradient Boosting Classifier often outperforms other models and it is possible to obtain an f1-score up to 0.903 using feature selection.