On June 1, 1972, the Department of the Army directed the Commanding General of Fort Benning, Georgia to grant Staff Sergeant (E-6) Kenneth L. Hodges an honorable discharge as soon as possible “for the convenience of the Government.” Then midway through his second six-year period of enlistment in the army, Sergeant Hodges was understandably unwilling to see his hopes for a military career so abruptly terminated, even for the price of an honorable discharge. Accordingly, on June 7, 1972, two days before the date set for his separation, Sergeant Hodges invoked the assistance of the United States District Court for the Middle District of Georgia.
As subsequent amendments to the pleadings made clear, the gravamen of Hodges’ complaint was that though ostensibly ordered “for the convenience of the Government,” the discharge was in fact designed as punishment for Hodges’ participation in the tragic events at My Lai 4, Republic of South Vietnam, on March 16, 1968.1 Recogniz*419ing that the Army’s actions did comply with the procedures established in Army Regulation [AR] 635-200 for discretionary “convenience discharges” and apparently conceding the constitutional validity of those procedures, Hodges insisted that in his case the Army should have followed the procedures outlined in AR 635-212 for discharges based on misconduct.2 Alleging that the pretextual “convenience” discharge contravened his right to due process of law, Hodges sought a temporary restraining order to halt his discharge pending a hearing on the merits of his claim and ultimately an injunction against his discharge pending compliance with the applicable regulations and “minimum concepts of fairness.”
For over a year the district court stayed the Army’s discharging hand in order to preserve the status quo pending disposition of the case on its merits. Following- an evidentiary hearing in May 1973, however, the district court on June 20, 1973, granted a partial summary judgment for defendants-appellees and dismissed Hodges’ complaint for failure to state a claim and for want of subject matter jurisdiction.3 Now a civilian,4 Hodges asks us to reverse the district court and order the Army to follow the procedures set forth in AR 635-212. Notwithstanding the importance of Hodges’ challenge to the action taken below, our attention to the merits of appellant’s position is deflected at the threshold by a jurisdictional problem not detected by either the parties or the district court.5
Although federal courts are not totally barred from barracks rooms and billets, our access is restricted. Writing for this Court in Mindes v. Seaman, 5 Cir. 1971, 453 F.2d 197, 201, Judge Clark framed a general statement of our authority:
a court should not review internal military affairs in the absence of (a) an allegation of the deprivation of a con*420stitutional right, or an allegation that the military has acted in violation of applicable statutes or its own regulations, and (B) exhaustion of available intraservice corrective measures.
The first portion of this formula may often be the more difficult to apply, for not all allegations technically within its perimeters are reviewable. Thus the trial court must “examine the substance of [the] allegation in light of the policy reasons behind nonreview of military matters,” balancing, inter alia, the nature and strength of the challenge to the military determination, the potential injury to the plaintiff if review is refused, the type and degree of anticipated interference with the military function, and the extent to which the exercise of military expertise or discretion is involved. Id. At the same time, concentration on the balancing act required to measure the sufficiency of the allegations should not obscure the importance of the second portion of the Mindes formula — the exhaustion requirement.
Beginning with McCurdy v. Zuckert, 5 Cir. 1966, 359 F.2d 491, cert. denied, 1966, 385 U.S. 903, 87 S.Ct. 212, 17 L.Ed.2d 133, this Court has firmly adhered to the rule that a plaintiff challenging an administrative military discharge will find the doors of the federal courthouse closed pending exhaustion of available administrative remedies. Accord, Davis v. Secretary of the Army, 5 Cir. 1971, 440 F.2d 817; Stanford v. United States, 5 Cir. 1969, 413 F.2d 1048; Tuggle v. Brown, 5 Cir., 362 F.2d 801, cert. denied, 1966, 385 U.S. 941, 87 S.Ct. 311, 17 L.Ed.2d 220. For purposes of this requirement, two types of administrative bodies provide review of discharge decisions.6 The Army Discharge Review Board [ADRB], established pursuant to 10 U.S.C. § 1553 (1974 Supp.) and 32 C.F.R. § 581.2 (1973), has authority to review the type of discharge given and to direct the Adjutant General to “change, correct, or modify any discharge or dismissal, and to issue a new discharge . ...” 32 C.F.R. § 581.2(a)(1) (1973). Established pursuant to 10 U.S.C. § 1552 (1970) and 32 C.F.R. § 581.3, the Army Board for Correction of Military Records [ABCMR] is to “consider all applications properly before it for the purpose of determining the existence of an error or injustice,” 32 C.F.R. § 581.3(b)(2) (1973), and may “correct any military record ... to correct an error or remove an injustice.” 10 U.S.C. § 1552(a).7
As previous decisions of this Court should have made clear, our basic exhaustion principle has two important corollaries. First, as with exhaustion of administrative remedies in other contexts, the exhaustion doctrine in review of military discharge decisions is subject to limitations or exceptions. The most important of these is that only those remedies which provide a real opportunity for adequate relief need be exhausted. Stated somewhat differently, exhaustion is inapposite and unnecessary when resort to the administrative reviewing body would be futile.8 For example, a plaintiff obviously need not appeal to *421the particular DRB or BCMR if the relief requested is not within the authority or power of those bodies to grant.9
The second corollary to our basic exhaustion principle is that having once determined the applicability of the exhaustion doctrine, a district court generally may not further entertain a complaint until the requirement is satisfied. If the suit was filed after discharge, the court may not retain jurisdiction while the plaintiff resorts to administrative review.10 And if the suit was filed before discharge, the court may not stay the discharge pending exhaustion of administrative remedies. This latter result is required by the authorizing statute in cases in which the desired relief falls within the bailiwick of the DRB, for those bodies are limited to post-discharge reviews, 10 U.S.C. § 1553(a) (1974 Supp.). This Court has also directed this result when the requested relief lies within the competence of a BCMR, notwithstanding the statutory authority of BCMR’s to entertain predischarge appeals and the willingness of some of those boards to do so if a court will stay discharge pending administrative review.11
Examination of the case sub judice in light of these two corollaries to the exhaustion doctrine clearly reveals the error below. Although appellant initially alleged that he had exhausted available intraservice remedies, it is quite clear that he has not yet attempted appeal to either the ADRB or the ABCMR. Appellees have conceded that Hodges need not approach the ADRB since that body deals only with changes in the type of discharge, whereas Hodges is complaining basically of the *422fact of discharge.12 They stoutly insist, however, that he should be required to appeal to the ABCMR. Unable to see any compelling reason to place this case within the category of cases generally excepted from the exhaustion requirement, we agree.
It seems quite clear to us that the ABCMR can, if it determines that Hodges has been illegally discharged, grant him full reinstatement and restoration of all rights, thus in effect making him whole for any injury he might suffer from a wrongful discharge.13 In addition, appellant Hodges complains of exactly the sort of injury for which the BCMR can supply effective and adequate balm.14 The gravamen of the complaint is that the Army did not follow the proper regulations in processing his discharge; whether this is viewed as a legal or a factual question, the Army ought to be the primary authority for the interpretation of its own regulations. A decision by the ABCMR that the Army should have followed AR 635-212 might completely obviate the need for judicial review. If, on the other hand, the ABCMR concludes that AR 635-212 is inapplicable to the facts of this case and Hodges then seeks judicial review, the court will at least have a definitive interpretation of the regulation and an explication of the relevant facts from the highest administrative body in the Army’s own appellate system. See Nelson v. Miller, 3 Cir., 373 F.2d 474, 480, cert. denied, 1967, 387 U.S. 924, 87 S.Ct. 2042, 18 L.Ed.2d 980; Sohm v. Fowler, 1966, 124 U.S.App.D.C. 382, 365 F.2d 915, 918-919.
Hodges argues that resort to the ABCMR in his case would obviously be futile and therefore ought not' be required. Since the Secretary of the Army ordered this discharge, Hodges insists, the ABCMR would be very reluctant to find any significant error in Hodges’ favor. Besides, the statute grants final approval over the Board’s decision to the Secretary, and he most certainly would not countermand himself, regardless of the Board’s recommendation,
Appellees offer several responses to this futility argument. Although we do not share their overly sanguine view regarding the efficacy of the intraservice administrative review procedures, we do agree that requiring Hodges to exhaust those remedies will not necessarily be an exercise in futility. According to the Army regulations implementing 10 U.S.C. § 1552, the ABCMR may not “deny an application *423on the sole ground that the record was made by or at the direction of the President or the Secretary in connection with proceedings other than proceedings of a Board for the correction of military or naval records.” 32 C.F.R. § 581.-3(c) (5) (ii). The BCMR’s action is subject to judicial reversal if it is arbitrary, capricious, unsupported by substantial evidence, or erroneous in law. Sanford v. United States, 9 Cir. 1968, 399 F.2d 693; Hoorwitz v. Resor, D. Conn., 329 F.Supp. 1050, aff’d, 2 Cir. 1970, 445 F.2d 1407; Esgate v. United States, 186 Ct.Cl. 207, cert. denied, 1968, 395 U.S. 913, 89 S.Ct. 1759, 23 L.Ed.2d 226. Moreover, though the Secretary may overrule the Board’s recommendations for relief, he cannot do so arbitrarily; if he rejects the Board’s recommendations, he must provide either explicitly stated policy reasons, or his action must be supported by the record and evidence presented to the Board. Nelson v. Miller, 3 Cir., 373 F.2d 474, cert. denied, 1967, 387 U.S. 924, 87 S.Ct. 2042, 18 L.Ed.2d 980; Weiss v. United States, 1969, 408 F.2d 416, 418, 187 Ct.Cl. 1, 5; Hertzog v. United States, 1964, 167 Ct.Cl. 377, 384-385; Proper v. United States, 1957, 154 F.Supp. 317, 326, 139 Ct.Cl. 511.15
In any event, to base an exception to the exhaustion requirement on the fact that the final administrative decision is subject to the discretionary power of the Secretary would in effect turn the exhaustion doctrine on its head. Exhaustion is required in part because of the possibility that administrative review might obviate the need for judicial review. That the administrative process might not have this effect is not usually a reason for bypassing it. And since the Service Secretary always has the final say over decisions by both the DRB and the BCMR, appellant’s futility reasoning would mean that exhaustion of intraservice remedies should always be excused. The administrative remedy available to grievants like appellant Hodges may offer cold comfort and small consolation, but it is surely beyond our authority to permit the exceptions to the exhaustion doctrine to swallow the rule.
We recognize, of course, that considerable resources, judicial as well as combatant, have been expended since this litigation began over two years ago. And mindful of Mr. Justice Black’s warning in another context against administrative procedures that exhaust the grievant before he can exhaust them, we are conscious of the burden on a plaintiff who at this stage of the game learns that he must begin anew at square one. Yet as serious as these considerations may be in Sergeant Hodges’ individual case, we do not believe they justify overriding the exhaustion requirement. The exhaustion doctrine rests on legitimate and important policy objectives relating to the balance between military authority and the power of federal courts.16 Adherence to the exhaustion requirement in cases presenting the type of challenge to administrative discharge decisions being mounted here will serve well these objectives.
For one thing, we can avoid premature court review that might upset the balance between the civilian judiciary and the military as a separate administrative and judicial system. We can prevent untoward, unreasonable interference with the efficient operation of the military’s judicial and administrative systems and allow the military an opportunity to exercise its own expertise and rectify its own errors before a court is called to render judgment. Moreover, we can guard, at least in the future, against inefficient' use of judicial resources by requiring “finality” within the military system and thus avoiding needless review.
Since the exhaustion requirement does apply in the instant case, our decisions in McCurdy v. Zuckert, supra, and Tug*424gle v. Brown, supra, command that the district court have no further jurisdiction over the case until the requirement be satisfied. Accordingly, we reverse the decision of the court below and remand the case with instructions to dismiss without prejudice for failure to exhaust intraservice administrative remedies.
We emphasize that our holding is only that Hodges approached the courthouse prematurely and that the court below erred in permitting him to enter without first surmounting the exhaustion hurdle. Hodges would synonomize pessimism with futility, but courts must — at least initially — indulge the optimistic presumption that the military will afford its members the protections vouchsafed by the Constitution, by the statutes, and by its own regulations. Certainly Kenneth L. Hodges did not surrender his right to due process of law when he doffed mufti. When he has completed his intraserviee appeals, he is free to return in search of judicial review. The barricade erected by the exhaustion requirement does not completely block the courtroom door.
Reversed and remanded.