Purpose: Recently introduced compressed sensing theory has enabled accurate, low‐dose CBCT reconstruction of anatomic information with fewer and noisier projections data. However, the reconstruction time remains a significant challenge for practical implementation in a busy clinic. We propose a novel gradient projection algorithm, based on Barzilai and Borwein formulation (GP‐BB), that handles the total variation (TV)‐norm regularization‐based least squares problem for CBCT reconstruction in an extremely efficient manner, with speed acceptable for use in on‐line IGRT. Methods: CBCT is reconstructed by minimizing the energy function consisting of 1) data fidelity term, and 2) TV‐norm regularization term. Both terms are simultaneously minimized by calculating the gradient projection of the energy function with the step size determined using an approximate second‐order Hessian calculation at each iteration, based on Barzilai and Borwein formulation. To speed up the process, a multi‐resolution optimization is used. In addition, the entire algorithm was designed to run with a single GPU card. To evaluate the performance, the CBCT projection data of a clinically‐treated head‐and‐neck patient was acquired from the Varian TrueBeam system. Results: The proposed GP‐BB algorithm was shown to be extremely efficient that a clinically reasonable patient image, using 120 CBCT projections, was reconstructed in 12 iterations for a total time of < 34 seconds. The image quality was visually equivalent to the commercial Feldkamp‐Davis‐Kress (FDK) algorithm using 364 CBCT projections. This represents dose reduction of one‐third (= 120/364) all at while maintaining the speed needed for clinical use. Conclusions: In this work, we developed a novel low‐dose CBCT reconstruction algorithm that is able to generate a clinically reasonable patient image in 12 iterations, using 120 CBCT projections, in total of < 34 seconds, with a single GPU card. This makes our GP‐BB algorithm entirely practical for daily clinical use.