We employ Data Envelopment Analysis to estimate the new technical, new cost, and new profit efficiency of Indian banks over the period 2008–2018. Then, we use Random Forest Regression to examine the impact of corporate governance (Board Size, Board Independence, Duality, Gender Diversity, and Board Meetings), bank characteristics (Return on Assets, Size, and Equity to Total Assets), and other characteristics (Ownership and Years) on bank efficiency. Among others, we found that board characteristics play a significant role particularly in new profit efficiency; therefore, policymakers and regulators should consider Board Size, Board Independence, Board Meetings, and Duality while framing guidelines for enhancing bank new profit efficiency. We also found that Board Independence plays a vital role in bank new cost efficiency, while Gender Diversity contributes to both new technical and new cost efficiency. This study makes methodological contributions by employing Machine Learning based Random Forest Regression in tandem with Data Envelopment Analysis under a two-phase model to examine corporate governance and bank efficiency, which is a pioneering attempt.