Ruth Boyd Hughes appeals the trial judge’s decision awarding custody of the parties’ two minor children to her husband, Richard Lee Hughes. The trial judge ordered a change in custody based upon a finding in a separate divorce proceeding that the wife committed adultery. For the reasons that follow, we reverse the custody decision.
I.
Custody of the children has shifted between the husband and the wife several times since their separation in 1995. On July 9, 1996, a judge of the Chesterfield County Juvenile and Domestic Relations District Court entered a custody order granting sole custody to the wife. A year later, another judge in the same court granted the husband sole custody of the children because the wife lived in a house with a man to whom she was not married. On appeal to the circuit court, the trial judge ruled, for those same reasons, that sole custody of the children should be with the husband.1 We reversed that *163decision and returned custody to the wife. In that decision, we provided the following summary of the facts:
The record before us shows that the parties separated due to various incidents of abuse by [the husband] often occurring in the presence of the two young children---On one occasion when the children were present in the same room, [the husband] threw [the wife] against the wall and held her there by her neck, leaving her with bruises. On *164another occasion, [the husband] threatened to kill both himself and [the wife] with a gun.
After leaving the home because of such abuse, [the wife] and the children moved in with her brother for a while and then to her parents’ home. Due to her father’s ill-health, she moved to a YMCA shelter and then to St. Joseph’s Villa, which provides housing for abused and homeless women and their children. She was asked to leave the shelter because [the husband] sent her a package which contained alcohol, a violation of the shelter’s rules. At this point Mike Kopeski, a co-worker of [the wife], offered to allow her and her children to stay in his home. In June 1996, Kopeski, [the wife] and her two children moved into a two bedroom house. She testified that because she had no car and insufficient income to support the boys and herself separately, she had no other options than to accept Kopeski’s offer. [The wife] denied having a sexual relationship with Kopeski, although she admitted being in love with him. She produced evidence that Kopeski slept in one bedroom and that she and her two sons slept in the other bedroom. She slept in the bottom bunk bed, one son slept in the top bunk, and the second son slept in a separate toddler bed in the room.
Hughes v. Hughes, Record No. 2565-97-2, 1998 WL 463323 (unpublished, Va.App. Slip op. at 2-3 Aug. 11, 1998). We also specifically noted that “[t]he [trial judge] found insufficient evidence to prove adultery.” Id., slip op. at 4.
Following our decision, the trial judge considered the parties’ divorce suit in a separate proceeding. Based upon the trial judge’s oral ruling that he was granting the husband a divorce on the ground of adultery, the husband petitioned for a change in custody. In the separate custody proceeding, the trial judge ruled that based on his finding in the divorce proceeding that the wife had committed adultery, sole custody of the children should be with the husband. The order changing custody was entered April 23, 1999, ten days before the final decree of divorce was entered on May 3, 1999. This appeal of the custody order followed.
*165II.
“In matters concerning custody and visitation, the welfare and best interests of the child are the ‘primary, paramount, and controlling consideration^].’ ” Kogon v. Ulerick, 12 Va.App. 595, 596, 405 S.E.2d 441, 442 (1991) (citation omitted); see also Walker v. Brooks, 203 Va. 417, 421, 124 S.E.2d 195, 198 (1962) (holding that “the best interests of the child are paramount and form the lodestar for the guidance of the court in determining the dispute”). “The authority vested in a trial [judge] to decide issues concerning the care [and] custody ... of ... children, the visitation rights of the noncustodial parent, and the extent to which those rights and responsibilities shall be apportioned between estranged parents is a matter of judicial discretion which courts must exercise with the welfare of the children as the paramount consideration.” Eichelberger v. Eichelberger, 2 Va.App. 409, 412, 345 S.E.2d 10, 11 (1986). “This best interests standard applies both to an initial determination regarding custody and to any subsequent requests for modification of custody.” Brown v. Brown, 30 Va.App. 532, 541, 518 S.E.2d 336, 340 (1999) (Elder, J., concurring and dissenting).
The “party seeking to modify an existing custody order bears the burden of proving” that a change in custody is appropriate. Id. at 537, 518 S.E.2d at 338. The test to be met “has two prongs: first, has there been a change in circumstances since the most recent custody award; second, would a change in custody be in the best interests of the children.” Keel v. Keel, 225 Va. 606, 611, 303 S.E.2d 917, 921 (1983).
The trial judge found “that there is a material change of circumstances embodied with the fact of the finding of adultery [in the divorce proceeding] by [the trial judge] that was not available at the time of [the trial judge’s] previous decision on the custody issue.” Initially, we note that when the husband filed his petition for custody alleging a change in circumstances, no final decree had been entered in the divorce proceeding. The husband relied upon the trial judge’s oral *166finding, which had not then been memorialized in a decree. Indeed, the custody order, which recited a finding of changed circumstances, was entered before the final decree of divorce was entered.
We also note that when we issued our opinion reversing the trial judge’s previous change of custody to the father, see Hughes v. Hughes, Record No. 2565-97-2 (unpublished August 11, 1998), the wife was already living in Kopeski’s house. She had moved into his house after living five months in a shelter for abused women. No new facts were proved in the most recent custody hearing that showed a change in that circumstance. Indeed, the record is replete with evidence that the wife’s housing status remained the same. The only changed circumstance was the trial judge’s ruling that in a separate proceeding he had made a finding of adultery, even though, on the same facts, he had not previously done so in the custody proceeding.
In the custody order from which this appeal arises, the trial judge ruled that the material change in circumstances was the finding of adultery that he had made in the separate divorce proceeding. In the appeal from the final decree of divorce, we have today reversed that decree and remanded the proceeding, see Hughes v. Hughes, 33 Va.App. 141, 531 S.E.2d 645 (2000); therefore, we hold that the trial judge erred in finding that the husband carried his burden in proving a change in circumstances. Because the trial judge erred as a matter of law in finding a change in circumstances, it is unnecessary to address the second prong of the Keel test. For these reasons, we reverse the trial judge’s change of custody order.
Reversed and dismissed.
. We relate in detail the trial judge’s findings at that earlier hearing: The Court finds both of these parties to be equally fit parents. I don’t find the living arrangements that exist here with regard to these children to show that [the wife] is an unfit mother.
I guess the question becomes this: How long do we have to wait to determine whether or not children are being adversely affected by a relationship in which there is a third party, unrelated male who could be the father of [the wife] living in the house. I don't believe I’m compelled to wait. These children are at very young, impressionable ages. These children are ages three and four and-a-half. This Court *163having dealt with many, many cases involving children in this age bracket is well aware of the fact that these children right now are at the developmental ages which are the most important formative years where the values and morals and mores that they will carry into adulthood are established. These children are at probably one of the most impressionable ages. And this Court is not pleased with what it views to be the moral climate and atmosphere that exists within that household.
Now, is there a provable case of adultery? No. I have to accept the evidence at face value in this case, but I don't believe it is incumbent upon this Court to wait until these children become adversely affected by a relationship that causes a questionable moral climate to exist within the household.
I'm going to award custody to the [husband]. I’m going to award visitation to the [wife] in accordance with the schedule that’s been established.
I will say based on the evidence that I have heard in this case, were it not for the living arrangements which [the wife] has maintained for over a year — and certainly given the explanation, it may have been understandable at one point in time when [the wife] needed shelter, she needed a place to go, she needed a place to take the children. She’s been in this relationship, living relationship, with a man, Mr. Kopeski, for well in excess of 15 months. I have heard no evidence whatsoever that [the wife] has sought to invoke the jurisdiction of this Court or any other court with regard to the issues of pendente lite support and maintenance, which would have been available to her to help her and assist her with regard to necessary living expenses for herself and the children through litigation. I have not heard that there has been any court of competent jurisdiction that’s been invoked in that regard.
The Court is of the opinion that the relationship, that the living arrangement, is more than one of more [sic] convenience. Were it not for that living relationship this Court would probably be more inclined to view the factors in this case as being persuasive of custody and support of [the wife].
I will not wait until the other shoe hits the ground to determine what the impact of this relationship is on the children, because it will be too late at that juncture.