To investigate changes of pulmonary nodules in temporal chest CT scans, we propose a novel technique for segmentation and registration of lungs. Our method is composed of the following steps. First, automatic segmentation is used to identify lungs in chest CT scans. Second, optimal cube registration is performed to correct gross translational mismatch of lungs. This initial registration does not require any anatomical landmarks. Third, a 3D distance map is generated by the narrow-band distance propagation, which drives fast and robust convergence to the optimum value. Fourth, the distance measure between surface boundary points is evaluated repeatedly by the selective distance measure (SDM). Then the final geometrical transformations are applied to ten pairs of successive chest CT scans. Fifth, nodule correspondences are established by the pairs with the smallest Euclidean distances. The performance of our method was evaluated with the aspects of visual inspection and accuracy. The positional differences between lungs of initial and follow-up CT scans were much reduced by the optimal cube registration. Then this initial alignment was refined by the subsequent iterative surface registration. For accuracy assessment, we have evaluated a root-mean-square (RMS) error between corresponding nodules on a per-center basis. The reduction of RMS error was obtained with the optimal cube registration, subsequent iterative surface registration and nodule registration. Experimental results show that our segmentation and registration method extracts accurate lungs and aligns them much faster than the conventional ones using a distance measure. Accurate and fast result of our method would be more useful for the radiologist’s evaluation of pulmonary nodules on chest CT scans.