Born in 1969, Paul was the eldest son of Audrey Trueman. The man he thought was his father, Patrick Trueman, abandoned Paul and Paul's younger brother Anthony during their childhood, and remained estranged from them. Paul was rebellious in his teens and engaged in crime, which upset his Christian mother; she believed that Paul would lead Anthony astray. Anthony achieved academically, unlike Paul, so when Anthony had a car crash while drunk and crippled a young girl, Paul took the blame and went to prison to save his brother. Audrey was allegedly unaware of this and disowned Paul.
Paul follows his mother and brother to Walford in 2001 after being estranged for them for some time. Audrey rejects him, but he decides to stay, blackmailing Anthony for money in exchange for keeping his drink-driving secret. Paul started playing in Steve Owen's poker games, when an old acquaintance of his, Angel Hudson, joins a game and instantly recognizes Paul. It transpires that Paul owes Angel money, and Angel threatens Paul's life unless he pays up. Paul tries to get the money by stealing property from his mother, pawning the goods and gambling the money he receives. This fails and he ends up with less money than he began with. When Angel comes to collect his money, Paul fails to pay, so Angel gives him a severe beating and trashes Audrey's bed and breakfast. After more threats from Angel, Paul blackmails Anthony into giving him the money. Anthony has no choice but to oblige; he takes out a loan and Paul pays Angel.
In September 2001, Audrey is struck by falling debris while walking past some building works. Several days later, after an argument with Paul during which he revealed Anthony was the one who was driving at the time of the accident, Audrey collapses and dies, caused by a delayed reaction to the blow she received earlier. Just before she dies, Audrey tells Paul that she knew about Anthony being the driver and tells Paul to tell Anthony that she loves him. Paul replies "What about me?". Just as Audrey is about to say something to him, she dies. However, everything is left to Paul in Audrey's will. Paul's supposed father Patrick Trueman arrives in Walford for her funeral. Paul initially reacts to Patrick with apprehension but they eventually bond. Both are devastated when Anthony discovers via DNA tests that Patrick is not Paul's biological father. Paul later discovers he is the biological child of Milton Hibbert, Patrick's friend with whom Audrey had been having an affair. Despite this, Patrick and Paul maintain a close relationship.
Angel returns in June 2002 with more orders for Paul. Angel is soon to stand trial for murder and is using his wife, Precious Hudson, as a fake alibi. He tells Paul to guard her until she could testify. Paul obliges and Precious moves to Albert Square. Paul and Precious begin an affair, but both fear repercussions from Angel. Precious refuses to be Angel's alibi, hoping that he will be imprisoned, but he is found not guilty. Paul and Precious make plans to flee the country, but Angel apprehends them stating that if he ever discovers they have resumed their relationship, he will kill them both. Precious has no choice but to finish with Paul and leave Walford alone.
In 2003, Paul is shocked when an abandoned baby is left on his doorstep. The child is the result of a one-night stand between Paul and a woman called Amy. Amy dumps her on Paul's doorstep, and he struggles to cope as a single parent. He names the baby Eleanor, after his stepfather, Patrick's mother. As Paul starts to cope with looking after Eleanor, Amy decides she wants her back and Social Services collect her, leaving Paul heartbroken.
In 2003, Paul begins sleeping with Janine Butcher; they concoct a plan to fleece Barry Evans of all his money. Janine professes to love Barry while all the time sleeping with Paul. Paul, however, attempts to stop the plan on Janine's wedding day to Barry confessing he loved her and they didn't need Barry's money but Janine refused. She marries Barry, thinking he is terminally ill so she can inherit his wealth, but the illness is a false alarm, and following the wedding, Janine confesses their marriage is a sham and pushes Barry away, repulsed; he falls down a ravine to his death. Paul suffers from immense guilt about his involvement in this. He finishes with Janine and in his guilt, makes a conscious effort to support Barry's grieving ex-wife Natalie Evans. Paul develops feelings for Natalie and they begin a relationship, but he struggles with his guilt. After Natalie grows suspicious of the nature of Paul's relationship with Janine, Paul finally reveals Janine's role in Barry's death and makes a statement to the police. Janine is questioned but released due to a lack of evidence. She promptly tells Natalie that Paul had conspired with her to "fleece" Barry from the start, and gloats about getting away with murder. Devastated, and unable to prove Janine's guilt to the police, Natalie leaves Paul and Albert square in Spring 2004.
Paul then decides to leave Walford and join his brother traveling Europe but returns to Albert Square to see Patrick and Yolande Trueman marry and is persuaded to stay in Walford. Paul has a spell working with troubled youth but begins to get involved in crime again in the latter part of 2004 when he starts drug dealing for Andy Hunter. After being arrested Paul informs the police about Andy's criminal dealings to the police, which proves to be his undoing, as Andy then orders him killed in December 2004. Paul considers escaping, but realizes his family would be in danger if he does, so he says a tearful goodbye to Patrick, leaving in a taxi; the driver of the taxi is a hitman, sent by Andy. Paul tells Patrick he is leaving and will not be seen again. Patrick is not aware that Paul is actually leaving to get killed. Paul asks the driver to "make it quick". A month later, when Patrick wants to find Paul after he fails to get in contact with him, he discovers Paul has been killed and identifies his corpse. He swears revenge on Andy and eventually gets his wish when Andy is killed in February 2005 by Johnny Allen.