*1374Opinion for the court filed by Circuit Judge REYNA. Dissenting opinion filed by Circuit Judge PROST.
REYNA, Circuit Judge.Rayland Young seeks review of the arbitrator’s opinion and award, dated August 31, 2011, denying his grievance that challenged his termination. For the reasons set forth below, we reverse the arbitrator’s decision and remand for further proceedings consistent with this opinion.
I. Background
Mr. Young served as a Public Housing Revitalization Specialist in the Office of Public Housing in the Cleveland, Ohio office of the Department of Housing and Urban Development (HUD). He had been employed by HUD for more than ten years. On August 31, 2010, Mr. Young was representing himself at an arbitration hearing, appealing his five-day suspension for disruptive behavior, misrepresentation of authority, and use of insulting language to and about other employees. One of the witnesses testifying against him was Gregory Darr, the Executive Director of the Coschocton Metropolitan Housing Authority and a HUD client.
Following Mr. Darr’s testimony, there was a recess in the proceeding. According to Mr. Darr, while he was walking down the hallway, about 25-30 feet away from Mr. Young, Mr. Young shouted from immediately outside the door of the hearing room, “[y]ou are a racist. You are a member of the KKK, and you should be shot.” Mr. Darr reported that he was shaken by the alleged incident, and he immediately relayed the events to an administrative officer, Reishmemah Haggins, and to the office manager, Doug Shelby. Mr. Darr also insisted on filing a statement with the Federal Protective Service. Mr. Darr did not identify any person who directly witnessed the alleged confrontation. In the days that followed the incident, distress within the office grew as word of the supposed confrontation spread. On September 3, 2010, Mr. Young was placed on administrative leave.
Shawn Sweet, Director of the Cleveland Hub Office of Public Housing prepared a proposal for disciplinary action to be taken against Mr. Young. Ms. Sweet determined that Mr. Young’s conduct was similar to Offense Five from the HUD Handbook No. 0752, “[r]ude boisterous, or disruptive conduct; use of insulting, abusive or offensive language to or about other employees,” but bordered on Offense Six, “[threatening behavior.” His threatening behavior was her key concern in recommending Mr. Young’s termination. But the reason Ms. Sweet gave for the punishment she recommended was that he “[made] an aggressive or intimidating statement to an Agency witness at an arbitration hearing.” Joint App’x 17.
Once Ms. Sweet issued her notice of proposed removal, Unabyrd Wadhams, Regional Public Housing Director, became the deciding official. Ms. Wadhams reviewed the proposal as well as the notes and supporting documents. She also interviewed several relevant witnesses, including Mr. Darr, Mr. Shelby, Ms. Hag-gins, and Jimmy Davis. Notably, Ms. Wadhams conducted all of her interviews after Mr. Young submitted his oral and written statements. This meant that Mr. Young was unaware of the content and substance of the interviews and was unable to respond to anything unearthed during those interviews.
Ms. Wadhams found Mr. Darr’s account of the incident credible, but its only support came from other individuals who relied on what Mr. Darr had told them about the incident. No witnesses testified that they either saw or heard Mr. Young yell or shout at Mr. Darr. In contrast, Mr. Davis, a HUD employee assisting Mr. Young in *1375the arbitration, submitted an affidavit on behalf of Mr. Young in which he stated, “I was with Mr. Young the entire time during this break. He never approached Mr. Darr and did not make any intimidating or aggressive statements to him. As a matter of fact he never said anything to Mr. Darr.” Joint App’x 35. During an interview held after Mr. Young made his submissions, Mr. Davis also testified that Mr. Young was in his view the entire break and that he did not witness Mr. Young scream, threaten, or otherwise interact with Mr. Darr. During the arbitration, HUD stipulated that Thomas Massouras, counsel for HUD at the hearing outside which the incident allegedly occurred, stayed in the hearing room during the entire recess and heard no confrontation or yelling. Consistent with these clear statements, Mr. Young and Mr. Davis maintained that they spent the entire recess outside the hearing room, while Mr. Davis later acknowledged in his interview that the two went to his cubicle during the recess and that he checked email and attended to other matters. Ms. Wadhams determined that this discrepancy wholly undermined Mr. Davis’ credibility as a witness and, as a result, Ms. Wadhams determined that Mr. Young engaged in the conduct described in Ms. Sweet’s proposal for removal. Mr. Young was never apprised of these supposed inconsistencies, nor did he have a chance to respond to them because the interview only occurred after Mr. Young had fully been heard.
In sustaining the recommendation to remove Mr. Young, Ms. Wadhams explained that she considered this as his second offense (the first being the conduct that gave rise to the five-day suspension). She viewed Mr. Young’s conduct as a very serious threat, and one that was particularly egregious because he directed it at a HUD client. She also explained that the language Mr. Young allegedly used was similar to language he allegedly used on other occasions, including the incident that gave rise to the prior appeal, so she treated those past incidents as evidence of a pattern of misconduct. On the basis of these considerations, Ms. Wadhams concluded that removal was the appropriate measure.
Following Ms. Wadhams’ decision, Mr. Young arbitrated his grievance before Marvin J. Feldman. The arbitrator found Mr. Darr’s testimony credible while Mr. Davis’ testimony was inconsistent and lacking in candor. As for the proposed penalty, the arbitrator also noted that this was Mr. Young’s second offense. But when discussing the first incident, the arbitrator described it as “nothing more than the predecessor of the activity involving the instant matter.” Joint App’x 12. Finally, regarding Mr. Young’s due process arguments, the arbitrator found them unfounded because he had been given adequate time at the end of his arbitration hearing to address them. The arbitrator found the charge against Mr. Young supported by preponderant evidence and denied the grievance. Following the arbitrator’s decision, Mr. Young appealed to this court. We have jurisdiction pursuant to 5 U.S.C. §§ 7121(f) and 7703.
II. Standard of Review
This court reviews an arbitrator’s decision, issued pursuant ‘to a negotiated grievance procedure, under the same standard that applies to appeals from the Merit Systems Protection Board. 5 U.S.C. § 7121(f) (2006); Dixon v. Dep’t of Transp., 8 F.3d 798, 803 (Fed.Cir.1993). Under that standard, we must affirm the arbitrator’s decision unless it is (1) arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law; (2) obtained without procedures required by law, rule, or regulation having been followed; or (3) unsupported by substantial *1376evidence. 5 U.S.C. § 7703(c); Dixon, 8 F.3d at 803. In addition, we must reverse an arbitrator’s decision if it is not in accordance with the requirements of the Due Process Clause of the Fifth Amendment or any other constitutional provision. Cf. Ward v. U.S. Postal Serv., 634 F.3d 1274, 1278 (Fed.Cir.2011).
III. Discussion
The proceedings leading to Mr. Young’s removal present serious concerns related to constitutional due process and observance of agency procedures, both of which the arbitrator failed to adequately address. In that order, we explain why each concern amounts to a violation and requires reversal.
A. Due Process
Procedural due process requires that certain substantive rights — including the property interest established by certain kinds of federal employment — cannot be deprived unless constitutionally adequate procedures are followed. Stone v. Fed. Deposit Ins. Corp., 179 F.3d 1368, 1375 (Fed.Cir.1999) (quoting Cleveland Bd. of Educ. v. Loudermill, 470 U.S. 532, 541, 105 S.Ct. 1487, 84 L.Ed.2d 494 (1985)). Applicable to this case are “[t]he essential requirements of due process, ... notice and an opportunity to respond.” Id. at 1375-76 (quoting Loudermill, 470 U.S. at 546, 105 S.Ct. 1487). As such, an employee is entitled to notice of the charges against him, an explanation of the employer’s evidence, and an opportunity to present his side of the story before termination. Id. at 1376 (quoting Loudermill, 470 U.S. at 546, 105 S.Ct. 1487); see also Douglas v. Veterans Admin., 5 MSPB 313, 5 M.S.P.R. 280, 304 (1981).
When an employer obtains new and material information through ex parte communications, an “employee’s constitutional due process guarantee of notice (both of the charges and of the employer’s evidence) and the opportunity to respond” are undermined. Stone, 179 F.3d at 1376. Where an employee has notice only of certain charges or portions of the evidence and the deciding official considers new and material information, procedural due process guarantees are not met because the employee is no longer on notice of the reasons for dismissal and/or the evidence relied upon by the agency. Id.
As we observed in Stone, not every ex parte communication is a procedural defect that is so substantial and so prejudicial as to undermine the due process guarantee and require an entirely new administrative proceeding. Rather, “only ex parte communications that introduce new and material information” to the deciding official violate the due process guarantee of notice. Id. at 1377.
In Stone, we identified several useful factors to consider when determining if new and material information has been introduced by means of ex parte contacts: (1) whether the ex parte communication introduces “cumulative” information or new information; (2) whether the employee knew of the communication and had a chance to respond; and (3) whether the ex parte communication resulted in undue pressure upon the deciding official to rule in a particular manner. Id. Where “the ex parte communication is so substantial and so likely to cause prejudice that no employee can fairly be required to be subjected to a deprivation of property under such circumstances,” a due process violation has occurred and the former employee is'entitled to a new constitutionally correct removal procedure. Id. Such a violation is not subject to the harmless error test. Id. (citing Sullivan v. Dep’t of the Navy, 720 F.2d 1266, 1274 (Fed.Cir.1983)).
Under the first Stone factor, HUD argues that the deciding official uncovered *1377cumulative, rather than “new and material,” information during her investigatory interviews of Mr. Darr, Mr. Shelby, Ms. Haggins, and Mr. Davis. HUD maintains that Blank v. Department of the Army, 247 F.3d 1225 (Fed.Cir.2001), authorizes such interviews to “confirm and clarify information that was already contained in the record.” Id. at 1229.
We are convinced that the ex parte communications in this case were more than “confirming and clarifying information” that was already on the record because the deciding official described the ex parte communication as a “huge” departure from written statements already on the record. The deciding official also admitted that the ex parte communications were the most critical statements in her mind. The significant and overwhelming role that the new communication played in the termination decision makes it evident that the ex parte communications introduced new and material information as understood under the first Stone factor.
As we observed in Ward — a case very similar to this one — the third Stone factor, undue pressure, is less relevant to determining whether the ex parte communications deprived the employee of due process where, as here, the deciding official admits that the ex parte communications influenced her determination. 634 F.3d at 1280 n. 2. Based on record admissions regarding the significance of the ex parte communications, the first Stone factor strongly suggests a due process violation while any deficiency of the third factor is less significant.
We also find HUD’s reliance on Blank misplaced for another reason. In that case, the Board actually analyzed the allegedly improper ex parte communications under the Stone factors, and this court found those findings supported by substantial evidence. Blank, 247 F.3d at 1229. In this case, the arbitrator performed no due process analysis whatsoever. Cf. Stone, 179 F.3d at 1377. Instead, the arbitrator merely noted that “[Mr. Young] received a full disclosure by the employer when requested ____ [and] ... was given, at the end of the hearing, sufficient time to reflect on his activities in the case.” Joint App’x 15. But the opportunity “to reflect on his activities” post-termination does not address whether Mr. Young had notice and an opportunity to be heard at the investigation stage. Instead, the controverted ex parte contacts arose after Mr. Young had made his written and oral statements to the deciding official. Mr. Young had no opportunity to respond to the allegedly inconsistent statements Mr. Davis had made only in his ex parte interview with the deciding official before the deciding official rendered her decision. This defect during the investigation stage more than satisfies the second Stone factor considering that Mr. Young neither learned of the ex parte communication, nor had an opportunity to respond to it before the deciding official. We also note the likelihood that any response from Mr. Young would have been meaningful in addressing the allegedly inconsistent statements. Given the layout of the HUD offices, the proximity of the hearing room to Mr. Davis’s cubicle, and the sworn testimony that Mr. Young was in view of Mr. Davis at all times, the perceived inconsistency in Mr. Davis’s statements appears easily reconcilable.
Mr. Young was entitled to “procedural fairness at each stage of the removal proceedings,” not just upon review of the termination decision. Stone, 179 F.3d at 1376. No amount of time for reflection can excuse past due process violations. “[W]hen these rights are undermined, [he] is entitled to relief regardless of the stage of the proceedings.” Id. We conclude as a matter of law that the ex parte communications from this case were so substantial *1378and so likely to cause prejudice that no employee can fairly be required to be subjected to a deprivation of property under these circumstances. Id. at 1377. A due process violation has occurred and Mr. Young is entitled to a new constitutionally correct removal procedure.1
B. Violation of Agency Procedures
Even if Mr. Young’s due process rights had not been violated, the deciding official’s conduct resulted in a harmful procedural error requiring reversal. Cf. Ward, 634 F.3d at 1281. Applicable regulations instruct the deciding official to “consider only the reasons specified in the notice of proposed action and any answer of the employee” in arriving at a removal decision. 5 CFR § 752.404(g)(1) (2012). Similarly, HUD’s Adverse Actions Handbook explains that a deciding official’s “decision must be based on the evidence relied upon to support the proposal, and not on ‘ex parte ’ (with only one side present) communications; i.e., conversation that provides additional evidence that is not provided to the employee for comment or response.” Dep’t of Housing and Urban Dev. Admin., Handbook 0752.02 REV-3, Adverse Actions (Dec. 1, 2000). “It is a procedural error ... for ‘an agency to rely on matters ... without including those matters in the proposal notice.’ ” Ward, 634 F.3d at 1281 (quoting Coleman v. Dep’t of Defense, 100 M.S.P.R. 574, 579 (2005)). Accordingly, because the deciding official relied on ex parte communications that were not part of the original proposal for removal, HUD committed procedural error. Id.
C. Evidence of Prior Misconduct
Finally, we believe that the deciding official and the arbitrator erred in basing their decisions — in part — upon similar instances of past misconduct. In particular, the deciding official explained that she found “Mr. Darr’s report ... credible because the language he reported [Mr. Young] using is similar to language that the record shows [he] ... used on other occasions, including those which have been the basis for prior discipline.” Joint App’x 22. Similarly, the arbitrator noted that “[t]here is no doubt in th[e] writer’s mind [Mr. Young] was responsible for the commentary to Darr at the time and place complained of. [Mr. Young’s] alleged activity was nothing more than a continuation of his behavior pattern that has followed the course of his presidency at the Cleveland HUD agency office.” Id. at 11.
The Board has previously held that, while prior misconduct may be considered in determining the appropriateness of a penalty or impeaching credibility where the prior misconduct relates to the propensity for honesty, reliance on prior conduct to prove whether the petitioner engaged in the same conduct on another occasion is inappropriate. See Carrick v. U.S. Postal Serv., 67 M.S.P.R. 280, 283, aff'd, 69 F.3d 555 (Fed.Cir.1995); see also Bennett v. Dep’t of the Air Force, 84 M.S.P.R. 132, 138 (M.S.P.B.1999); Hawkins v. Smithso*1379nian Inst., 73 M.S.P.R. 397, 403 (M.S.P.B. 1997). Similarly, in Ibrahim v. Department of the Army, 30 M.S.P.R. 531, 536 (1986), the Board, looking to Federal Rule of Evidence 404(a) for guidance, stated that “[t]he basic rule is that character evidence may not be introduced circumstantially to prove the conduct of the witness.” We agree. While the Federal Rules of Evidence do not apply to Board hearings, we have found them to be a helpful guide to proper hearing practices. Yanopoulos v. Dep’t of Navy, 796 F.2d 468, 471 (Fed.Cir.1986). On remand, Mr. Young’s past misconduct should not be used to prove charges that have been asserted against him in this case. Mr. Young’s identity is not at issue here and the government’s reliance on Federal Rule of Evidence 404(b) to excuse this use of character evidence is without merit.
IV. Conclusion
Because we conclude that Mr. Young’s due process rights have been violated and that the agency violated its own procedures, we reverse the arbitrator’s decision and remand for further proceedings consistent with this opinion. Given this disposition, we need not address the other grounds for relief asserted by the petitioner.
REVERSED AND REMANDED
Costs
No costs.
. The dissent accuses the majority of wearing blinders in our review of the termination proceeding. The problem with this perspective is that the dissent, like the deciding officer below, starts from the position that Mr. Young indisputably engaged in the behavior of which he is accused, relying on prior experiences, the truth and veracity of which were not adjudged below or brought on appeal. See, e.g., dissent at 1379 ("Young is not a stranger to disciplinary proceedings.”); see also id. at 1379 n. 1 (crediting the unsubstantiated "fears” of Mr. Young's co-workers). Thus, the dissent concludes that the ex parte communications were harmless procedural errors that merely "confirmed” Mr. Young's behavior. We believe the record evidence on that point is sufficiently in dispute that Mr. Young’s due process rights must be safeguarded.