OPINION OF THE COURT
RENDELL, Circuit Judge.Anthony Robertson appeals from an order of the District Court that revoked his term of supervised release. We conclude that the District Court erred when it failed to conduct a preliminary hearing before revoking Robertson’s supervised release, as Rule 32.1(b)(1)(A) of the Federal Rules of Criminal Procedure requires. However, because Robertson was not prejudiced by that error, we conclude that his “substantial rights” were not affected and he is not entitled to relief under plain error review. As a result, we will affirm the order of the District Court.
I.
In October 2006, Anthony Robertson pleaded guilty to Count One of a superseding indictment which charged him with being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g)(1). The District Court sentenced him to twenty-four months of imprisonment, to be followed by three years of supervised release. Robertson was released from prison in December 2007, but was arrested three months later by McKeesport, Pennsylvania police (Lieutenant Hanna) on charges of possession with intent to deliver cocaine. In March 2008, Robertson was arrested again, this time in Pittsburgh on firearm and marijuana possession charges. Thereafter, the District Court issued an arrest warrant based on Robertson’s apparent violations of his supervised release.
Robertson’s initial court appearance for the violations took place before a magistrate judge on November 24, 2008. A supervised release revocation hearing was scheduled for December 9, 2008, but Robertson was granted a continuance until January 13, 2009. At Robertson’s request, a status conference was held on that day, wherein Robertson complained about his lawyer’s performance and expressed to the District Court that he feared for his safety in prison. Robertson was granted a continuation of his revocation hearing until January 22, 2009.
At the revocation hearing, Lieutenant Hanna testified to the events leading up to Robertson’s arrest in McKeesport. Hanna testified that he observed, from approximately six feet away, Robertson make a hand-to-hand drug transaction outside a local bar, and then drive away (as the passenger) in a car. Hanna testified that after the car was pulled over by another officer, Hanna searched the car and found a bag of suspected cocaine base between the front seats. After that, Hanna arrested Robertson. Approximately two hundred dollars was found on Robertson’s person.
Hanna was cross-examined by Robertson’s attorney. Against his attorney’s advice, Robertson testified at the revocation hearing. He testified that he had not en*303gaged in a drug transaction, and that he had no idea who owned the cocaine base found in the car he had been riding in. Robertson testified on cross examination that his fiancé had given him the money that was found on his person.
The District Court concluded by a preponderance of the evidence that Robertson had engaged in a drug transaction, in violation of both state and federal law. Accordingly, the District Court issued an order revoking Robertson’s supervised release. It ordered Robertson to serve twenty-four months of imprisonment, to be followed by twelve months of supervised release. Robertson appealed, claiming for the first time that the District Court violated Rule 32.1(b)(1)(A) of the Federal Rules of Criminal Procedure by failing to conduct a preliminary hearing before revoking his term of supervised release. Robertson argues that this failure constituted a violation of his due process rights.
II.
Pursuant to 18 U.S.C. § 3583(e)(3), the District Court had plenary jurisdiction to revoke Robertson’s term of supervised release. Our jurisdiction arises under. 28 U.S.C. § 1291. Because Robertson failed to preserve at the revocation hearing his objection to the lack of a preliminary hearing, we review the decision of the District Court for plain error. United States v. Adams, 252 F.3d 276, 278 (3d Cir.2001). Under plain error review, we may grant relief if the District Court committed an “error” that was “plain” and affected Robertson’s “substantial rights.” Fed. R.Crim.P. 52(a); see United States v. Olano, 507 U.S. 725, 732, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993). A “deviation from a legal rule is an error,” and that “error” is “plain” when it is “clear or obvious.” United States v. Plotts, 359 F.3d 247, 249 (3d Cir.2004) (internal quotations omitted). An error has affected “substantial rights” when it has been prejudicial, i.e., when it has “affected the outcome of the district court proceedings.” Id. (quoting Olano, 507 U.S. at 734, 113 S.Ct. 1770). We only exercise our discretion to correct that error if it “seriously affects the fairness, integrity or public reputation of judicial proceedings.” Id.
III.
Rule 32.1 of the Federal Rules of Criminal Procedure provides for two hearings before a term of supervised release can be revoked: “one a preliminary hearing at the time of his arrest and detention to determine whether there is probable cause to believe that he has committed a violation of his [supervised release], and the other a somewhat more comprehensive hearing prior to the making of the final revocation decision.” Gagnon v. Scarpelli, 411 U.S. 778, 781-82, 93 S.Ct. 1756, 36 L.Ed.2d 656 (1973) (relying on Morrissey v. Brewer, 408 U.S. 471, 92 S.Ct. 2593, 33 L.Ed.2d 484 (1972)). The rule codifies the due process protections recognized in Gagnon and Morrissey, and it explains step-by-step the procedures that a district court must follow before revoking or modifying a term of supervised release.
Specifically, once in custody, a person accused of violating his term of supervised release “must be taken without unnecessary delay before a magistrate judge.” Fed.R.Crim.P. 32.1(a)(1). The magistrate judge must inform the person of the alleged violation, the person’s right to counsel, and “the person’s right, if held in custody, to a preliminary hearing under Rule 32.1(b)(1).” Fed.R.Crim.P. 32.1(a)(3). That preliminary hearing must be promptly conducted by the magistrate judge. Fed.R.Crim.P. 32.1(b)(1)(A). The substance of the preliminary hearing must consist of the following:
*304(1) an opportunity to appear and present evidence; and
(2) upon request, an opportunity to question any adverse witness, unless the judge determines that the interest of justice does not require the witness to appear.
Fed.R.Crim.P. 32.1(b)(1)(B). The purpose of the preliminary hearing is to determine whether there is probable cause for the alleged violation of supervised release, and concomitantly whether a revocation hearing will be held. Fed.R.Crim.P. 32.1(b)(1)(A) and (C).
The parties agree, and the record confirms, that Robertson did not receive a preliminary hearing before his term of supervised release was revoked.1 The District Court’s failure to conduct a preliminary hearing was a clear deviation from Rule 32.1(b)(1)(A). Nevertheless, under our standard of review, Robertson’s claim must fail: he has not shown that the District Court’s error affected his “substantial rights” because he has failed to demonstrate how the lack of a preliminary hearing caused him prejudice.2 Nor has Robertson shown that the District Court’s error “should be presumed prejudicial, or that the error belongs in a special category of errors that should be corrected regardless of prejudice (ie., the category of structural errors).” Plotts, 359 F.3d at 249 (quoting Adams, 252 F.3d at 285-86).
Robertson had a full and fair opportunity to contest the facts underlying the charges against him: he received written notice of the claimed violations of supervised release, he was able to cross-examine the sole adverse witness, and he testified to his own version of the facts leading up to his arrest in McKeesport. Robertson has not identified any witnesses he was unable to call, or documentary evidence he was unable to present, due to the lack of a prehminary hearing. Moreover, Robertson does not claim that the absence of a preliminary hearing somehow affected his sentence for the violation of supervised release. Viewed together, the aforementioned facts demonstrate that the lack of a preliminary hearing did not “affect[ ] the outcome of the district court proceedings” in this case. Plotts, 359 F.3d at 249.
At oral argument we were told by both parties that the provisions of Rule 32.1, and in particular those concerning preliminary hearings, are ignored with some regularity in the Western District of Pennsylvania. This is troubling. The United States Court of Appeals for the Second Circuit had similar concerns in United States v. Companion, 545 F.2d 308 (2d Cir.1976), where it cautioned as follows:
our decision does not give the Government license to ignore the preliminary hearing mandate of Morrissey and Gagnon. If a probationer’s rights are flagrantly abused, or if preliminary hearings are repeatedly denied to probationers as a group, we reserve, of course, the authority, as a matter of our supervisory power, to order release from custody regardless of when the request is made.
Id. at 313.
We echo those words in the context of Robertson’s case. It should go without *305saying that a district court should not pick and choose which Rule 32.1 rights to afford a person charged with a violation of his supervised release; the mandatory nature of the Rule’s provisions is made abundantly clear by the use of the word “must” throughout.
With that in mind, and for the reasons given above, we will AFFIRM the Order of the District Court.
. Robertson was not advised of his “right'' to a preliminary hearing during his initial appearance, in violation of Rule 32.1(a)(3), as well.
. Robertson's ability to show prejudice would still be the focal inquiry were we not conducting plain error review. See United States v. Santana, 526 F.3d 1257, 1260 (9th Cir.2008) (due process claims rooted in revocation proceedings require showing of prejudice); see also United States v. Chaklader, 987 F.2d 75, 77 (1st Cir.1993).