Accurate lung tumor segmentation is a prerequisite for effective radiation therapy and surgical planning. However, tumor delineation is challenging when the tumor boundaries are indistinct on PET or CT. To address this problem, we developed a segmentation method to improve the delineation of primary lung tumors from PET-CT images.We formulated the segmentation problem as a label information propagation process in an iterative manner. Our model incorporates spatial-topological information from PET and local intensity changes from CT. The topological information of the regions was extracted based on the metabolic activity of different tissues. The spatial-topological information moderates the amount of label information that a pixel receives: The label information attenuates as the spatial distance increases and when crossing different topological regions. Thus, the spatial-topological constraint assists accurate tumor delineation and separation. The label information propagation and transition model are solved under a random walk framework.Our method achieved an average DSC of 0.848 ± 0.036 and HD (mm) of 8.652 ± 4.532 on 40 patients with lung cancer. The t test showed a significant improvement (p value < 0.05) in segmentation accuracy when compared to eight other methods. Our method was better able to delineate tumors that had heterogeneous FDG uptake and which abutted adjacent structures that had similar densities.Our method, using a spatial-topological constraint, provided better lung tumor delineation, in particular, when the tumor involved or abutted the chest wall and the mediastinum.