BOYCE F. MARTIN, Jr., Circuit Judge.

This case requires us to balance the need for expeditious resolution of employment discharge cases and the employer’s right to a full and fair adjudicative process. In this case, Yellow Freight System, Inc., challenges the Secretary of Labor’s decision that Yellow Freight violated 49 U.S.C. App. § 2305(a), which is part of the Surface Transportation Assistance Act of 1982. In this opinion, 49 U.S.C. App. § 2305(a) and 49 U.S.C. App. § 2305(b) will be referred to as § 405(a) and § 405(b), respectively, which are the section numbers used by Congress in the original act. In support of their challenge, Yellow Freight argues (1) the Secretary incorrectly interpreted § 405(a), and (2) the Secretary violated its due process rights by refusing to reopen the administrative hearing. For the following reasons, we refuse to enforce the Secretary’s decision.

Yellow Freight is a large interstate trucking company with several hundred terminals nationwide. Yellow Freight hired Thomas E. Moyer, the complainant, as a truck driver in 1978. On February 29, 1988, Yellow Freight dispatched Moyer from its Richfield, Ohio, terminal to pick up a truck. While returning to the terminal, Moyer’s truck suffered a mechanical breakdown. Moyer contacted a Yellow Freight dispatcher who instructed him to go to the *355 nearest telephone and, presumably, inform the company’s mechanics of his situation.

As Moyer descended from the truck, he aggravated a pre-existing medical condition. Moyer contacted the dispatcher who once again told Moyer to go to a telephone, call the mechanics, and return to the truck to await help. Another Yellow Freight driver stopped to assist Moyer and eventually drove him to the terminal. At the terminal, Moyer told the dispatcher that he was ill and needed to go to a hospital. The dispatcher insisted that Moyer inform company mechanics of the breakdown and report the location of the truck. Eventually an ambulance arrived and medical personnel transported Moyer to the hospital.

After the incident, Yellow Freight placed Moyer on a four-day suspension for returning to the terminal and leaving the truck unattended and for failing to follow company procedure for drivers experiencing mechanical breakdowns. Between June and October 1988, Yellow Freight issued Moyer four warning letters for being unavailable for dispatch without an excuse. The final warning concerned Moyer’s absence on October 5, 1988. On that date Moyer testified at a grievance proceeding for Robert E. Lee, a fellow employee. In this proceeding, Lee challenged Yellow Freight’s decision to fire him following his receipt of a letter from Yellow Freight that allegedly gave him 72 hours to appear at the terminal. Moyer testified that Lee had a back injury and had been unable to respond to the company’s demand. After issuing this letter concerning Moyer’s October 5 absence, Yellow Freight terminated Moyer on November 9, 1988.

On November 14, 1988, Moyer filed a complaint with the Secretary of Labor alleging that Yellow Freight had violated § 405 of the Surface Transportation Assistance Act by discharging him in retaliation for his refusal to drive a truck while he was ill on February 29, 1988. In a letter dated November 30, 1988, the Department of Labor’s Occupational Safety and Health Administration notified Yellow Freight of the complaint, and requested the following information:

[A] full and complete written account of the facts and a statement of your position in respect to the allegation that Mr. Moyer was discharged on November 9, 1988 in reprisal for not operating his commercial vehicle because of illness.

Subsequently, in a letter dated March 17, 1989, OSHA’s regional administrator informed Yellow Freight of his findings. He stated:

The U.S. Department of Labor has completed its investigation of the complaint of Thomas E. Moyer, a former employee, who alleged that your company discriminated against him in violation of section 405(b) of the Surface Transportation Assistance Act of 1982 (49 U.S.C. 2310 et seq.). As set forth in the enclosed Findings, I have determined that Mr. Moyer’s complaint has no merit.

Moyer objected to OSHA’s findings and requested an administrative hearing. After an evidentiary hearing, an administrative law judge recommended the Secretary find no violation of § 405(b) because on February 29, 1988, Moyer was not engaged in any activity protected by that provision. The administrative law judge noted that although Moyer testified that he believed his discharge may have also resulted from his testimony in the Lee grievance proceeding, there were insufficient evidence on the nature of the Lee proceeding to find a violation of another provision, § 405(a).

After reviewing the record, the Secretary agreed with the administrative law judge that Yellow Freight’s discharge of Moyer did not violate § 405(b). The Secretary, however, contrary to the finding of the administrative law judge, concluded Moyer’s discharge violated § 405(a). The Secretary found that Yellow Freight discharged Moyer in retaliation for his testimony at Lee’s grievance hearing, and that the nature of Lee’s hearing rendered Moyer’s testimony protected under § 405(a). The Secretary concluded there was sufficient evidence in the record as a whole to determine Mr. Lee’s grievance proceeding related to a violation of a commercial motor vehicle safety rule. The Secretary stated:

*356 The proceeding need only be “related to” a safety violation. The violation need not comprise the only or even the predominant subject of the proceeding. Here, [Lee] testified that during the 72-hour period in question he “was bedfast” on “serious” medication due to “back problems.” He believed that the medication and illness impaired his ability to work. As a driver for [Yellow Freight] his primary duty was the operation of commercial motor vehicles. [Yellow Freight] directed [Lee] to report to work, vehicle operation in violation of 49 C.F.R. § 392.3 being the anticipated work assignment. The record is devoid of any evidence, and [Yellow Freight] has not argued, that it intended to assign [Lee] nondriving duties. I deem [Lee’s] grievance proceeding, wherein he challenged being discharged when too ill and impaired to report, to be sufficiently related to a safety violation to afford [Moyer] protection for his testimony about [Lee’s] health.

(citations and footnotes omitted). The Secretary ordered Yellow Freight to reinstate Moyer, and remanded the case to the administrative law judge for a determination of the appropriate relief.

Prior to remand, Yellow Freight filed a petition with this court alleging a violation of due process and requesting a review of the Secretary’s Decision and Order of Remand. This court abstained from reviewing the case until the Secretary either ruled on Yellow Freight’s motion to vacate the Decision and Order of Remand or attempted to enforce the order. The Secretary eventually denied the company’s motion to vacate and refused to reopen the administrative hearing.

The Secretary issued her Final Decision and Order on September 27, 1990. On October 26, 1990, Yellow Freight filed a second petition with this court seeking review of the Secretary’s decision finding a violation of § 405(a) as well as her order denying reopening of the administrative hearing. For purposes of review, we consolidated Yellow Freight’s second petition with their original petition.

Congress enacted § 405 of the Surface Transportation Assistance Act “to encourage employee reporting of noncompliance with safety regulations governing commercial motor vehicles.” Brock v. Roadway Express, Inc., 481 U.S. 252, 258, 107 S.Ct. 1740, 1745, 95 L.Ed.2d 239 (1987). Congress recognized that employees in the transportation industry were the best source of information regarding safety violations and also realized that these employees needed protection against employer retaliation. Id.

Section 405 contains two provisions relevant to the disposition of this case. Section 405(a) prohibits a commercial motor carrier from discharging, disciplining, or discriminating against an employee in retaliation for filing a complaint or starting a proceeding relating to a violation of a commercial motor vehicle safety provision, or for testifying in such a proceeding. 49 U.S.C.A. App. § 2305(a). Section 405(b) prohibits a commercial motor carrier from discharging, disciplining, or discriminating against an employee who refuses either to operate a commercial motor vehicle he believes is unsafe or to operate the vehicle under conditions that would violate any federal provision applicable to commercial motor vehicle safety or health. 49 U.S.C.A. App. § 2305(b).

On appeal, Yellow Freight first argues that the Secretary incorrectly interpreted § 405(a). In an order denying Yellow Freight’s motion to vacate, the Secretary, in interpreting § 405(a), stated:

[Protection for Mr. Moyer would not depend on whether Mr. Lee prevailed on his claim. Similarly, protection would not depend on a finding that Mr. Lee actually operated, or was required or permitted by a motor carrier to operate, a vehicle while ill or fatigued. Rather, the purpose of preserving unobstructed channels of information is served if individuals are protected for providing testimony concerning possible violations.

The statutory “relating to” language does not restrict protection to participation in ST A A proceedings. Rather, protection extends to employees who *357 have filed any complaint or instituted or testified in any proceedings relating to a violation of a spectrum of safety criteria.

(citations and footnotes omitted). Yellow Freight asserts that under the Secretary’s interpretation of § 405(a) the actual facts involved in the Lee proceeding are irrelevant to determining whether Moyer engaged in a protected activity by testifying at Lee’s grievance hearing. The company contends such an interpretation would bring within the scope of § 405(a) almost any case in which an employee’s illness is tangentially at issue.

Under the Surface Transportation Assistance Act, we are bound by the Secretary’s legal conclusions unless they are arbitrary, capricious, involve an abuse of discretion, or otherwise are not in accordance with law. See 49 U.S.C. App. § 2305(d)(1) (incorporating by reference 5 U.S.C. § 706(2)). We give deference to the Secretary’s interpretation of a statute that Congress has charged her with administering. See Whiteside v. Secretary of Health and Human Services, 834 F.2d 1289, 1293 (6th Cir.1987) (quoting Federal Election Comm’n v. Democratic Senatorial Campaign Comm’n, 454 U.S. 27, 31-32, 102 S.Ct. 38, 41-42, 70 L.Ed.2d 23 (1981)). Thus, we will uphold the Secretary’s interpretation of § 405(a) if the interpretation is reasonable, consistent with the statutory mandate, and persuasive. Id.

After reviewing the statutory language, we believe the Secretary correctly interpreted § 405(a). Yellow Freight’s assertions notwithstanding, as we read the Secretary’s interpretation, she clearly does not posit that the actual facts surrounding Lee’s grievance hearing are irrelevant to § 405(a) protection. Under the Secretary’s interpretation, Moyer’s § 405(a) protection is not dependent upon whether Lee was actually successful in proving a violation of a federal safety provision. The primary consideration is not the outcome of the underlying grievance hearing, but whether the proceeding is based upon possible safety violations. We agree with the Secretary’s interpretation because we find it reasonable, consistent with the statutory mandate, and persuasive.

Next, we face a more difficult issue raised by Yellow Freight: whether the Secretary deprived Yellow Freight of due process by finding a violation of § 405(a) and refusing to reopen the administrative hearing to allow evidence on the § 405(a) issue. Yellow Freight alleges the Secretary found the company guilty of violating § 405(a) without giving it prior notice of a § 405(a) charge and a corresponding opportunity to respond to the charge.

The fundamental elements of procedural due process are notice and an opportunity to be heard. Mullane v. Central Hanover Bank & Trust Co., 339 U.S. 306, 313, 70 S.Ct. 652, 656, 94 L.Ed. 865 (1950). Congress incorporated these notions of due process in the Administrative Procedure Act. Under the Act, “[p]ersons entitled to notice of an agency hearing shall be timely informed of ... the matters of fact and law asserted.” 5 U.S.C. § 554(b). To satisfy the requirements of due process, an administrative agency must give the party charged a clear statement of the theory on which the agency will proceed with the case. Bendix Corp. v. FTC, 450 F.2d 534, 542 (6th Cir.1971). Additionally, “an agency may not change theories in midstream without giving respondents reasonable notice of the change.” Id. (quoting Rodale Press, Inc. v. FTC, 407 F.2d 1252, 1256 (D.C.Cir.1968)).

NLRB v. Homemaker Shops, Inc., 724 F.2d 535 (6th Cir.1984) is illustrative of these principles. In Homemaker Shops, the complaint alleged only that the employer had unlawfully assisted the union. Id. at 542. During an evidentiary hearing, the Board’s attorney reiterated the same allegation. Under these circumstances, we held that the Board could not find the company guilty of the distinct charge of unlawfully dominating the union. We stated:

“The fundamental fairness inherent in administrative due process cannot permit the [government] to plead a certain charge, insist at hearing that only that charge is being litigated, and then raise a *358 related, but more onerous charge only after the hearing record is closed.”

Id. at 544. Compare Grand Rapids Die Casting Corp. v. NLRB, 833 F.2d 605, 606 (6th Cir.1987) (finding no due process violation when the Board found the company guilty of firing a union steward for threatening to file charges, but complaint alleged that company fired the steward because she had filed charges).

On the record before us, we conclude that prior to the administrative hearing, the Secretary failed to give Yellow Freight adequate notice of a § 405(a) issue. The letter from OSHA notifying the company of Moyer’s complaint referred only to Yellow Freight’s discharge of Moyer in retaliation for not operating his vehicle because of illness, which is a § 405(b) issue, Moyer’s written complaint does not- give any indication that he was complaining that Yellow Freight fired him for testifying in a safety-related hearing. OSHA’s letter to Yellow Freight conveying OSHA’s findings after the preliminary investigation also characterized Moyer’s complaint in terms of § 405(b). Finally, Moyer’s objections to these findings set forth only a § 405(b) issue. Thus, prior to the administrative hearing neither the Department of Labor nor Moyer had given Yellow Freight notice of a possible § 405(a) issue.

Notwithstanding the possible lack of notice prior to the administrative hearing, due process is not offended if an agency decides an issue the parties fairly and fully litigated at a hearing. When parties fully litigate an issue they obviously have notice of the issue and have been given an opportunity to respond. This satisfies the requirement of administrative due process. “[T]he test is one of fairness under the circumstances of each case — whether the employer knew what conduct was in issue and had an opportunity to present his defense.” Soule Glass and Glazing Co. v. NLRB, 652 F.2d 1055, 1074 (1st Cir.1981). Focusing on this theme, the Secretary contends that Yellow Freight impliedly consented to litigate a § 405(a) issue. The Secretary argues that at the hearing Moyer “clearly” raised a § 405(a) issue by introducing evidence that established the company discharged him for testifying at a safety-related grievance proceeding. The Secretary argues that when Yellow Freight failed to object to the introduction of this evidence, under Fed.R.Civ.P. 15(b) and 29 C.F.R. § 18.43(c), which has similar language to Rule 15(b), the company impliedly consented to litigate the § 405(a) issue.

The general rule is when issues not raised in pleadings are raised by the express or implied consent of the parties, the court may treat the issues in all respects as if the parties had raised them in the pleadings. Fed.R.Civ.P. 15(b); 29 C.F.R. § 18.-43(c). Thus, if an issue is tried fully by the parties, a court or agency may base its decision on that issue and may deem the pleadings amended accordingly, even though the parties did not set forth the theory in the pleadings. MBI Motor Co., Inc. v. Lotus/East, Inc., 506 F.2d 709, 711 (6th Cir.1974). “This rule is designed to allow parties ... to get to the heart of the matter and not have relevant issues obscured by pleading niceties. It was not designed to allow parties to change theories in mid-stream.” Donald v. Wilson, 847 F.2d 1191, 1198 (6th Cir.1988).

We caution that a trial court or agency may not base its decision upon an issue the parties tried inadvertently. Implied consent is not established merely because one party introduced evidence relevant to an unpleaded issue and the opposing party failed to object to its introduction. It must appear that the parties understood the evidence to be aimed at the unpleaded issue. MBI Motor Co., 506 F.2d at 711. Also, evidence introduced at a hearing that is relevant to a pleaded issue as well as an unpleaded issue cannot serve to give the opposing party fair notice that the new, unpleaded issue is entering the case. Wesco Mfg., Inc. v. Tropical Attractions, 833 F.2d 1484, 1487 (11th Cir.1987). Compare Haught v. Maceluch, 681 F.2d 291, 805 (5th Cir.1982) (implied consent to try an issue can exist when a party fails to object to the introduction of evidence relevant only to an unpleaded issue).

*359 In this case, we do not believe that Moyer clearly raised the issue of a § 405(a) violation or that Yellow Freight did or should have understood that some of the evidence was directed at a § 405(a) issue. Hence, we do not believe Yellow Freight impliedly consented to litigate the issue. Granted, the Secretary points us to a few fragments of testimony extracted from a 150-page transcript and argues that Moyer clearly raised a § 405(a) issue. We note that the Secretary provides us with some fragments of testimony out of the context in which they were made and that most of these fragments of testimony are relevant to a § 405(b) violation as well as a § 405(a) violation and, therefore, the Secretary cannot use them to demonstrate Yellow Freight impliedly consented to try a § 405(a) violation. After examining the remaining fragments of testimony and the transcript as a whole, we do not believe that implied consent existed in this case to try a § 405(a) issue. We do not doubt that implied consent can exist in a given case; however, implied consent does not exist under the facts in this case.

In summation, the Secretary found Yellow Freight guilty of violating § 405(a) without giving the company prior notice of a possible § 405(a) issue. Yellow Freight did not impliedly consent to try the § 405(a) issue during the administrative hearing and did not, in fact, try the issue; therefore, the Secretary did not give Yellow Freight an opportunity to respond before finding a violation of § 405(a). Taking these factors into consideration, we find the Secretary’s actions violated Yellow Freight’s due process rights.

Finding that the Secretary violated Yellow Freight’s due process rights, we refuse to enforce the Secretary’s order. On remand, the Secretary can re-examine the § 405(a) issue after giving Yellow Freight proper notice and a full and fair opportunity to respond.