We develop a theory of optimal stopping problems under G-expectation framework. We first define a new kind of random times, called G-stopping times, which is suitable for this problem. For the discrete time case with finite horizon, the value function is defined backwardly and we show that it is the smallest G-supermartingale dominating the payoff process and the optimal stopping time exists. Then we extend this result both to the infinite horizon and to the continuous time case. We also establish the relation between the value function and solution of reflected BSDE driven by G-Brownian motion.