As machine learning becomes prevalent in our daily lives involving a widening array of applications such as medicine, finance, job hiring and criminal justice, one morally legally motivated need for machine learning algorithms is to ensure fairness for disadvantageous against advantageous groups. Fairness in machine learning aims at guaranteeing the irrelevancy of a prediction output to sensitive attributes like race, sex and religion. To this end, we take an information- theoretic approach using mutual information (MI) which can fully capture such independence. Inspired by the fact that MI between prediction and the sensitive attribute being zero is the "sufficient and necessary condition" for independence, we develop an MI-based algorithm that well trades off prediction accuracy for fairness performance often quantified as Disparate Impact (DI) or Equalized Odds (EO). Our experiments both on synthetic and benchmark real datasets demonstrate that our algorithm outperforms prior fair classifiers in tradeoff performance both w.r.t. DI and EO.