Mr. Robert J. Milanak seeks review of a final order of the Merit Systems Protection Board (Board) denying Mr. Milanak’s petition for review of an administrative judge’s initial decision dismissing Mr. Milanak’s appeal. Milanak v. Dep’t of Transp., MSPB Docket No. CH-315H-01-0041-B-l, 93 M.S.P.R. 304 (Sept. 17, 2002). Although designated as a dismissal for failure to state a claim upon which relief could be granted, this was actually a decision on the merits after a hearing. This court affirms.
I.
On October 12, 1999, Mr. Milanak was hired as a motor carrier safety specialist for the Federal Motor Carrier Safety Administration (Safety Administration) of the Department of Transportation (the agency) in Springfield, Illinois, subject to a one-year probationary period. On February 18, 2000, Mr. Milanak submitted to the agency a declaration for federal employment form disclosing that the Immigration & Naturalization Service (INS) had previously terminated him. In June 1998, the INS terminated Mr. Milanak from his position as Deportation Officer for mistreat*325ing a person in custody, for making a false statement to a supervisor, and for making a false statement during an official investigation. Following Ms termination from the INS, Mr. Milanak filed an individual right of action appeal with the Board, wMch the Board ultimately dismissed for lack of jurisdiction.
In August 15, 2000, the agency stated in an internal memorandum that Mr. Milanak was “suitable for employment ... as he presents himself as a competent employee who works hard.” On September 5, 2000, Mr. Milanak’s supervisor at the Safety Admimstration wrote Mr. Milanak stating that he would be terminated effective September 15, 2000, for failing to properly conduct a compliance review, repeatedly reportmg to work late without authorization, and failing to follow office guidelines for scheduling compliance reviews.
Mr. Milanak appealed Ms termination to the Board, wMch issued an imtial decision dismissmg the appeal for lack of jurisdiction. Mr. Milanak filed a petition for review of the imtial decision. On October 18, 2001, the Board vacated the imtial decision and remanded to the regional office. The Board found that Mr. Milanak had raised a non-frivolous allegation that the agency terminated Mm for pre-appointment reasons without followmg the procedures required for such termination. See 5 C.F.R. § 315.805 (2003).
On remand, the admimstrative judge conducted a hearing and Mr. Milanak elected not to testify. The agency supplemented the record with evidence about why it terminated Mr. Milanak. Mr. Milanak filed two motions to compel discovery about an alleged negative suitability determination of Mr. Milanak by the agency. On January 10, 2002, the admimstrative judge demed the motions, ruling that the requested evidence was not relevant because the Board found no non-frivolous allegation of a negative suitability determination. On February 20, 2002, the administrative judge issued an rnitial decision dismissing the appeal. The administrative judge found that Mr. Milanak had failed to prove that he was terminated for preemployment reasons and thus 5 C.F.R. § 315.805 did not apply.
Mr. Milanak filed a timely petition for review of the imtial decision. On September 17, 2002, the Board concluded that there was no legal error and no new, previously unavailable evidence, and demed the petition for review. Mr. Milanak appeals that decision to this court.
II.
TMs court sustains a final decision of the Board unless it is arbitrary, capricious, an abuse of discretion or otherwise not in accordance with law. When the Board’s final decision rests on fact-finding supported by substantial evidence, tMs court must accept those facts as true. See 5 U.S.C. § 7703(c) (2000). TMs court reviews for abuse of discretion a Board ruling on procedural matters such as discovery. Curtin v. Office of Pers. Mgmt., 846 F.2d 1373, 1378 (Fed.Cir.1988).
III.
In the final order of September 17, 2002, the Board concluded that there was no new, previously unavailable evidence before it and that the admimstrative judge made no error in law or regulation. Mr. Milanak does not contend and tMs court does not find that there was new, previously unavailable, evidence before the Board. Absent such evidence or error, the Board correctly demed the petition for review. See 5 C.F.R. § 1201.115(d) (2002).
Mr. Milanak contends that the Board erred in denying Ms two motions to compel discovery and m denying him a *326jurisdictional hearing. This court discerns no error in the Board’s actions. Mr. Milanak filed the motions to uncover evidence that the agency terminated him based on a negative suitability determination. But the Board found that Mr. Milanak had not raised a non-frivolous allegation of a negative suitability determination, and correctly concluded that any evidence about the issue would be irrelevant. The Board therefore did not abuse its discretion in denying Mr. Milanak’s motions to compel discovery. The Board also did not err in denying Mr. Milanak a jurisdictional hearing. See Dick v. Dep’t of Veterans Affairs, 290 F.3d 1356, 1361-62 (Fed.Cir.2002) (stating that the Board properly establishes jurisdiction by the written record and that “[tjhere is no right to a hearing on the threshold issue of jurisdiction”).
Mr. Milanak also contends that the administrative judge erred in ruling on the merits of this case and in determining witness credibility.
A probationary employee may only appeal an agency’s termination decision if the employee alleges that the decision was based on partisan politics or marital status, or that the termination was for preappointment reasons and the agency did not follow required termination procedures. See 5 C.F.R. §§ 315.805, 315.806 (2003). An administrative judge’s credibility determination is “virtually unreviewable” on appeal. Bieber v. Dep’t of Army, 287 F.3d 1358, 1364 (Fed.Cir.2002).z
Mr. Milanak does not allege termination based on partisan politics or marital status. Instead, he alleges that the agency terminated him for pre-appointment reasons without following the required procedures for such cases.
On remand from the Board’s decision of October 18, 2001, the administrative judge found that the agency supplemented the record with evidence showing that the agency did not terminate Mr. Milanak for pre-appointment reasons. The administrative judge considered Safety Administration state director Mr. John Muleare’s testimony that Mr. Milanak’s performance started deteriorating in July 2000. Mr. Mulcare testified that Mr. Milanak made field trips to motor carriers for compliance reviews without notifying the motor carriers in advance, contrary to agency policy. To support this testimony, the agency presented documents showing that Mr. Milanak scheduled visits to two motor carriers that were not in business. Mulcare also testified that a compliance review that Mr. Milanak had conducted was deficient for failing to cite numerous violations, and that when questioned about the review Mr. Milanak said that he had “screwed up.”
Mr. Milanak’s training coach Mr. Jimmy Fox corroborated Mr. Muleare’s testimony. Mr. Fox testified that Mr. Milanak’s performance deteriorated in August 2000, in that Mr. Milanak arrived to work late on several occasions and Mr. Milanak’s compliance reviews were deficient.
Mr. Mulcare also testified that Mr. Milanak’s INS history was not a factor in terminating him. Douglas Sawin, midwest field administrator and the reviewing official for terminating Mr. Milanak, corroborated Mr. Muleare’s testimony. Mr. Sawin testified that Mr. Mulcare never mentioned Mr. Milanak’s INS history and that Mr. Sawin did not consider Mr. Milanak’s INS history when he agreed to the termination of Mr. Milanak.
The administrative judge found Mr. Muleare’s testimony credible and found no evidence contradicting Mr. Muleare’s and Mr. Sawin’s testimony that they did not consider pre-appointment reasons in deciding to terminate Mr. Milanak. This court finds no basis in the record for rejecting *327the administrative judge’s credibility determination.
In sum, substantial evidence supports the administrative judge’s findings that the agency had valid reasons to terminate Mr. Milanak and that the agency did not rely on pre-appointment reasons. The administrative judge therefore did not err in concluding that the procedures set forth in 5 C.F.R. § 315.805 do not apply and properly dismissed the case.