Paul first met Curtis Holt as his physical therapist when the latter suffered from Achilles tendinitis and needed it treated for his training to qualify for the Olympics. Because of Curtis's impatience, it took Paul a while to get him to focus on his actual recovery.
After Curtis was fired from Palmer Technologies, he mentioned how Paul was always saying how he wanted to go on a trip, and Curtis supposed that his recent unemployment gave them the time and opportunity to finally do so.
Paul later attended Oliver Queen and Felicity Smoak's holiday party with Curtis. They revealed that they had been married for five years and Paul proposed by placing a ring in the reef while they were scuba diving for Curtis to find.
Paul and Curtis also later attended the couple's engagement party. After Curtis gave Felicity the bio-stimulant implant that would help her walk again, Paul told her how much work Curtis had put into the gift.
After Felicity first received the implant that would help her walk again, she met with Paul as her physical therapist to help her through the process.
Paul began to feel worried that Curtis may never make it home alive, after he began his vigilante activities. During the City Hall Christmas party, Paul was witness to Prometheus attacking and taking down Curtis, which put him in the hospital. Paul visited Curtis after he woke up, and told him that he could no longer handle Curtis being both his husband and being Mr. Terrific at the same time. He told Curtis to choose before leaving. Less than 24 hours later, Curtis comes home and sees that Paul has packed his belongings and is moving out. Paul moves out to his brother's house, leaving Curtis devastated.
A few months later, Paul meets with Curtis at a restaurant and tells him that he is divorcing him and sadly leaves him.