To implement and evaluate a block matching registration (BMR) algorithm for automatic registration of locally advanced lung tumors during image‐guided radiotherapy. Small (1 cm³), non‐overlapping image sub‐volumes (“blocks”) were identified on the tumor surface of the planning image (13 to 282 blocks per image) and were independently and automatically registered to the on‐treatment image using a rigid transform. A multi‐resolution strategy was implemented for improved speed and accuracy. At each resolution, multiple potential displacement vectors were initially permitted for each block. Then, after registering all blocks, the final set of transforms (one per block) was iteratively determined to maximize the local displacement consistency across immediately neighboring blocks. Finally, the optimal rigid transform for the on‐treatment image was extracted, providing the patient setup correction. This algorithm was evaluated for 18 locally‐advanced lung cancer patients, each with 4 to 7 weekly on‐treatment CT scans having physician‐delineated gross tumor volumes (GTV). Volume overlap was computed as the intersection of planning and registered GTVs divided by the registered GTV. Border displacement errors (BDE) were also calculated in the left‐right (LR), anterior‐posterior (AP) and superior‐inferior (SI) directions, from which the required margins were computed. Implementation of multi‐resolution registration reduced initial block matching errors by 39%. By also permitting multiple potential displacements per block, initial errors were reduced by 65%. After BMR, LR, AP, and SI systematic BDE were 3.2, 2.4, and 4.4 mm respectively, with random BDE of 2.4, 2.1, and 2.7 mm. Required margins included both localization and delineation uncertainties and ranged from 5.0 to 11.7 mm, an average of 40% less than required for bony alignment. BMR is a promising approach for automatic lung tumor localization. Further evaluation is warranted to assess the accuracy and robustness of BMR against other potential localization strategies. This work was supported by NIH grant R01CA116249.