A new method for reconstructing phylogenetic relationships of within-host (patient) viral evolution from noncontemporaneous samples is presented. This method has two important features: noncontemporaneous viral samples can be dealt with by a simple computing algorithm, and both neutral and adaptive evolution patterns occurring during the process of viral evolution can be estimated. In our previous study, we proposed a preliminary formulation of this algorithm that was based on the maximum likelihood method. However, that preliminary formulation was difficult to use because the calculation of the likelihood required an extremely large amount of time and the number of possible tree topologies increased exponentially according to the increase in the number of viral variants. In this paper, we propose another new algorithm, referred to as a distance-based sequential-linking algorithm, in which the neighbor-joining method is employed for reconstruction of the longitudinal phylogenetic tree from serial viral samples. This algorithm is applied to a longitudinal data set of the env gene (V3 region) of human immunodeficiency virus type 1 (HIV-1) obtained over 7 years after the infection of a single patient. The results suggest that this method can successfully reconstruct a longitudinal phylogenetic tree from noncontemporaneous viral samples within a reasonable calculation time. This revised method proved to be a useful tool for estimating the dynamic process of within-host viral evolution.