Verifying the correct functioning of quantum gates is a crucial step toward reliable quantum information processing, but it becomes an overwhelming challenge as the system size grows due to the dimensionality curse. Recent theoretical breakthroughs show that it is possible to verify various important quantum gates with the optimal sample complexity of O(1/ε) using local operations only, where ε is the estimation precision. In this Letter, we propose a variant of quantum gate verification (QGV) that is robust to practical gate imperfections and experimentally realize efficient QGV on a 2-qubit controlled-not gate and a 3-qubit Toffoli gate using only local state preparations and measurements. The experimental results show that, by using only 1600 and 2600 measurements on average, we can verify with 95% confidence level that the implemented controlled-not gate and Toffoli gate have fidelities of at least 99% and 97%, respectively. Demonstrating the superior low sample complexity and experimental feasibility of QGV, our work promises a solution to the dimensionality curse in verifying large quantum devices in the quantum era.