Plaintiff, a male registered nurse employed at a Veterans Administration Medical Center in upstate New York was found, after an administrative hearing, on a single occasion to have verbally abused a patient. For this infraction of the rules as set forth in the agency’s policy manual, the Secretary of Veterans Affairs (Secretary), accepting the administrative decisions and recommendations of subordinate officials of the Department of Veterans Affairs (VA), terminated plaintiffs employment. When the district court vacated the Secretary’s decision, the VA appealed.
The VA’s apparent objective, like that expressed by Gilbert and Sullivan in the “Mikado”, is to let the punishment fit the crime.1 We know this is the VA’s objective not only because it accords with basic notions of fairness, but because the VA’s policy manual itself also so provides. Nonetheless, the principal question before us is whether the VA followed this policy and adopted a punishment that fits the offense.
BACKGROUND
William Ward worked as a registered nurse with psychiatric patients at the Veterans Administration Medical Center in Canan-daigua, New York from December 14, 1981 until he was discharged on December 3,1990. He was fired after two nursing assistants and a registered nurse who was Ward’s supervisor filed written incident reports alleging that nearly two weeks earlier, on March 31, 1989, Ward had verbally abused three patients. The record indicates that on the morning of the alleged incidents Ward had reprimanded the two nursing assistants for leaving a suicidal patient with a shaving razor unattended while they smoked cigarettes in a shower room, in violation of VA policies. The record also shows that Ward was an active union officer and had filed numerous grievances against his supervisor for unfair labor practices. A three-member panel conducted an administrative investigation between April 21 and July 7,1989, and concluded all three incidents were substantiated. It recommended Ward be discharged.
The Associate Deputy Chief Medical Director of the Veterans Administration Department of Medicine and Surgery (Department) sent Ward a letter of proposed discharge on September 25, 1989. Plaintiff ex*518ercised his rights under 38 U.S.C. § 4110 (1988)2 and requested a hearing before the Department’s Disciplinary Board (Board). The Board, comprised of three nurses from other VA facilities, conducted a hearing from March 19 to 21, 1990. It determined that only one of the three charges against Ward was sustained. But it specifically found Ward had committed major patient abuse by “intentionally teasing, speaking harshly to, and threatening and intimidating the patient,” and recommended discharge as the penalty. The Chief Medical Director adopted the Board’s decision and recommendation as his own. In December 1990 Ward appealed the Chief Medical Director’s decision to the Secretary.
While the appeal was pending, Ward’s union submitted to the Secretary an opinion of an Administrative Law Judge (ALJ) of the Federal Labor Relations Authority in a related unfair labor practice proceeding. This action had been brought by Ward’s union on his behalf and on behalf of David Bellomo, another employee at the Canandaigua facility whom the Department recommended discharging at about the same time as Ward. In his opinion, the ALJ found that he had no jurisdiction to hear the claims, but that if he could have heard them, he “would conclude that the General Counsel has established by a preponderance of the evidence that the proposed discharges of Ward and Bellomo were motivated by their protected activity” and that even if some disciplinary action were warranted, discharge would not have been proposed in the absence of their union activities.
The 26 page opinion also documented action taken against other Canandaigua employees for allegations of patient abuse, which revealed that no such employee had ever been discharged. The VA responded that the Secretary would consider the ALJ’s findings. But the Secretary sustained the Chief Medical Director’s decision and ordered plaintiffs termination of employment.
Several months later in April 1991 Ward brought suit in the United States District Court for the District of Columbia against the VA, the Secretary of Veterans Affairs, and the Director of the Veterans Administration Medical Center (defendants or appellants). He sought review of the Secretary’s decision under the Administrative Procedure Act (APA), 5 U.S.C. §§ 701-706 (1988), and claimed violations of his First and Fifth Amendment rights. Ward asked the district court for a reversal of the Secretary’s decision, reinstatement, back pay, the cleansing of his record, costs and attorney fees. The parties filed cross motions for summary judgment. The district court — believing a trial necessary on the First Amendment claims, which would require substantial testimony from witnesses located in New York— transferred the case to the Western District of New York, where both parties renewed their motions for summary judgment.
The District Court for the Western District (Larimer, J.) granted in part and denied in part the parties’ motions. It first found jurisdiction to hear the appeal because although decisions of the Secretary are “final” under 38 U.S.C. § 7462, the Secretary did not persuade the district court by clear and convincing evidence that Congress intended to preclude judicial review of his decisions. Second, the district court held that the Secretary’s ruling that Ward’s conduct with respect to one of the charged incidents constituted patient abuse was not arbitrary and capricious. But third, the trial court ruled that to impose a penalty of discharge was arbitrary and capricious in light of the policy in the VA Personnel Policy Manual (VA Manual). That policy requires the Department to treat similar offenses with similar penalties and to penalize employees in proportion to the offense committed.
In its third ruling, the district court placed great weight on examples it found in the ALJ’s opinion of much more egregious conduct by other Department employees that did not result in their discharge. The district court therefore remanded the case to the Secretary to redetermine the appropriate penalty. It did not reach Ward’s constitu*519tional claims or his request for back pay, but retained jurisdiction over the case.
DISCUSSION
As a threshold matter, appellants insist the district court had no jurisdiction over Ward’s suit and that its order must therefore be vacated. Were the case properly in the district court, they maintain as a second point, the discharge penalty imposed by the Secretary was not arbitrary and capricious. In concluding that the Secretary’s decision was arbitrary, appellants continue, the trial court wrongly considered materials that had not been considered in the first instance by the Board, and restricted its review of Department penalties imposed only to those employees working at the Canandaigua facility. Appellants assert, as a third issue, that it was error for the court to decide the penalty was excessive, instead of leaving that decision to the Secretary or to the Board on remand. In the discussion that follows, we deal with each of these issues.
I Jurisdiction
Defendants for the first time on appeal declare that Ward’s suit was not properly before the district court because he sought monetary relief from the United States in excess of $10,000, and under the Tucker Act, 28 U.S.C. §§ 1346, 1491 (1988 & Supp. IV 1992), his claims for relief belong within the exclusive jurisdiction of the Court of Federal Claims. The VA defendants are entitled to raise this issue for the first time on appeal because it has been the rule since nearly the inception of our republic that subject matter jurisdiction may be raised any time. See Mansfield, Coldwater & Lake Mich. R.R. v. Swan, 111 U.S. 379, 382, 4 S.Ct. 510, 511, 28 L.Ed. 462 (1884) (citing Capron v. Van Noorden, 6 U.S. (2 Cranch) 126, 2 L.Ed. 229 (1804) as the genesis of the rule). While we agree that the Court of Federal Claims would have had jurisdiction over Ward’s suit had he chosen to bring it in that forum, we are unable to adopt defendants’ view that the Tucker Act divests a federal district court of its original jurisdiction over claims against the government for more than $10,000 when the claim is based on a statute, other than the Tucker Act, containing a waiver of sovereign immunity.
The Tucker Act grants jurisdiction to the United States Court of Federal Claims to decide claims against the United States founded either upon the Constitution, a federal statute, or any regulation of an executive department. See 28 U.S.C. § 1491(a)(1). Since Ward’s suit is against an agency of the United States and is founded on a federal statute, namely the statute governing discipline of Department senior employees, 38 U.S.C. §§ 7461-7464, his action was subject to the jurisdiction of the Court of Federal Claims.
Nonetheless, the Tucker Act also provides that when the amount in controversy in a suit against the United States does not exceed $10,000, the federal district courts have original jurisdiction concurrent with the Court of Federal Claims. The Act states: “The district courts shall have original jurisdiction, concurrent with the United States Court of Federal Claims, of: ... [a]ny ... civil action or claim against the United States, not exceeding $10,000 in amount_” 28 U.S.C. § 1346 (1988 & Supp. IV 1992). Defendants read this section as giving an exclusive grant of jurisdiction to the Court of Federal Claims in cases involving more than $10,000. We rejected such a limited construction of the Tucker Act in C.H. Sanders Co. v. BHAP Housing Development Fund Co., 903 F.2d 114 (2d Cir.1990).
In addressing the scope of the Tucker Act in C.H. Sanders, we held that regardless of the amount in controversy, an action in a district court is proper under the federal question jurisdiction statute, 28 U.S.C. § 1331, if a statute other than the Tucker Act provides the necessary waiver of sovereign immunity. See C.H. Sanders, 903 F.2d at 119. Thus, although an action could have been brought in the Court of Federal Claims under the Tucker Act, a district court has jurisdiction over the case so long as there is both a grant of subject matter jurisdiction and an independent waiver of sovereign immunity exists. See Jackson Square Assocs. v. United States Dep’t of Hous. & Urban Dev., 797 F.Supp. 242, 244 (W.D.N.Y.1992); see also Falls Riverway Realty, Inc. v. City *520of Niagara Falls, 754 F.2d 49, 54 (2d Cir.1985).
Here the district court concluded it had subject matter jurisdiction under the APA, 5 U.S.C. §§ 701-706, to review the Secretary’s final decision made pursuant to 38 U.S.C. § 7462. Appellants have not appealed this ruling; but it remains their position that no statute other than the Tucker Act provides a waiver of sovereign immunity as to all of Ward’s claims.
A. The Administrative Procedure Act
The APA entitles “person[s] suffering legal wrong because of agency action, or adversely affected or aggrieved by agency action within the meaning of a relevant statute ... to judicial review thereof.” 5 U.S.C. § 702. In 1976 Congress amended the APA to add the following language:
An action in a court of the United States seeking relief other than money damages and stating a claim that an agency or an officer or employee thereof acted or failed to act in an official capacity or under color of legal authority shall not be dismissed nor relief therein be denied on the ground that it is against the United States or that the United States is an indispensable party.
Id. (emphasis supplied). The Supreme Court has interpreted this legislative language as providing a valid waiver of sovereign immunity in cases covered by the amendment to the APA. See Bowen v. Massachusetts, 487 U.S. 879, 891-92, 108 S.Ct. 2722, 2730-31, 101 L.Ed.2d 749 (1988). Hence, to the extent that Ward sought relief other than money damages — declaratory and injunctive relief— his claims were properly before the district court. See id. at 893, 108 S.Ct. at 2731. But the APA does not waive sovereign immunity for money damages claims. Back pay, as a claim for money damages, falls outside the scope of the APA. See Hubbard v. Administrator, EPA 982 F.2d 531, 533 (D.C.Cir.1992) (en banc). Insofar as Ward’s claim sought back pay, therefore, it was not properly before the district court unless Congress waived sovereign immunity for such claim in another statute.
B. The Back Pay Act
Ward contends that such a waiver of sovereign immunity for back pay claims against the United States is found in the Back Pay Act of 1966, 5 U.S.C. § 5596 (1988). That Act provides a federal government employee is entitled to back pay if “found by appropriate authority under applicable law, rule, regulation, or collective bargaining agreement, to have been affected by an unjustified or unwarranted personnel action which has resulted in the withdrawal or reduction of all or part of the pay, allowances, or differentials of the employee.” See id. § 5596(b)(1). The Supreme Court reads the Back Pay Act as a statute that mandates compensation by the federal government in a successful suit against the government. See Bowen, 487 U.S. at 905 n. 42, 108 S.Ct. at 2738 n. 42. “The Back Pay Act is the means by which appointed employees subjected to unjustified personnel action are given a cause of action against the United States.” United States v. Hopkins, 427 U.S. 123, 128, 96 S.Ct. 2508, 2511, 49 L.Ed.2d 361 (1976). Such a cause of action is limited by the terms of the Back Pay Act to employees who have been unlawfully “subjected to a reduction in their duly appointed emoluments or position.” United States v. Testan, 424 U.S. 392, 407, 96 S.Ct. 948, 957, 47 L.Ed.2d 114 (1976).
We read these binding cases as interpreting the Back Pay Act to provide an explicit waiver of sovereign immunity in cases covered by that Act. Accord Brown v. Secretary of Army, 918 F.2d 214, 216 (D.C.Cir.1990) (Back Pay Act waives sovereign immunity against prejudgment interest on Title VII back pay awards). But see Mitchell v. United States, 930 F.2d 893, 896 n. 3, 897 (Fed.Cir.1991) (Service member’s suit for back pay falls within claims court’s Tucker Act jurisdiction and does not lie in district court).
We think Ward’s claim for back pay falls within the terms of the Back Pay Act. He has alleged that a federal government agency, the VA, has subjected him to a personnel action that has resulted in the withdrawal of his pay. If the agency action is determined to have been unwarranted, then Ward will be entitled to back pay and the Back Pay Act *521provides him the necessary consent to enforce this right in federal district court.
II Merits
Having resolved the jurisdictional issue, we pass to the merits. Appellants challenge several aspects of the district court’s decision. Before discussing them, we look for a moment at the scope of our review. On appeal from a district court’s review of an APA claim, an appellate court accords no deference to the lower court’s decision, see Hanson v. Espy, 8 F.3d 469, 472 (7th Cir.1993); Sierra Club v. Davies, 955 F.2d 1188, 1192 (8th Cir.1992), but instead conducts de novo review of the administrative record and renders its own independent judgment. The APA permits us to set aside the agency action only if it is “arbitrary, capricious, an abuse of discretion, or otherwise not in accordance with law.” 5 U.S.C. § 706(2)(A). Although narrow, appellate review of an administrative record must nonetheless be careful, thorough and probing. See Blassingame v. Secretary of Navy, 866 F.2d 556, 559 (2d Cir.1989).
A. The Penalty
Analysis of the merits begins with the penalty of discharge recommended by the Board and adopted on appeal by the Secretary. At the time of the disciplinary proceeding against Ward, the Board was required by statute to recommend a penalty within the limitations prescribed by the Secretary. These penalties range from the lightest, a reprimand, move up to suspension and reduction of pay, and go to the heaviest penalty, discharge from employment. See 38 U.S.C. § 4110(d). The regulations prescribed by the Secretary are found in the VA Manual and its Department of Medicine and Surgery Supplements.
The VA Manual governs disciplinary action taken against certain full-time Department employees, including registered nurses like Ward. See VA Manual, MP-5, Pt. II, ch. 8, sec. 0 — 1. It mandates that once the Board has sustained a charge against an employee, it must recommend a penalty appropriate to the offense, and that in all cases where a penalty is recommended, “the principle of like penalties for like offenses will apply.” Id. sec. C-5(a). Discharge is a penalty that may be appropriately imposed in cases of patient abuse. See id. Department Supp., fig. 8A.01. Yet, there is no evidence in the administrative record before us that the Board considered — much less applied— the policy of like penalties for like offenses.
With regard to the penalty chosen, the Board considered the so-called Douglas Factors, enumerated by the Merit Systems Protection Board as “relevant for consideration in determining the appropriateness of a penalty.” Curtis Douglas, 5 M.S.P.B. 313, 5 M.S.P.R. 280, 304-06 (1981). The Board’s decision merely states,
The Disciplinary Board considered several issues as cited in the Douglas Factors ... in reaching its recommendation as to what administrative action is indicated. Specifically, the Disciplinary Board determined that the Douglas Factors #1, #2, #7, and #11, were applicable to this ease. The Disciplinary Board recommends that William Ward, R.N. be discharged from the Department of Veterans Affairs.
The Board did not find Douglas Factor # 6— “consistency of the penalty with those imposed upon other employees for the same or similar offenses” — to be applicable. Id. at 305. More importantly, the Board when selecting the penalty failed to refer to the VA Manual instructions given it, including the like penalties for like offenses policy. It was arbitrary and capricious for the Board not to consider the Secretary’s regulations, as prescribed under 38 U.S.C. § 4110(d), when arriving at a penalty to mete out to a Department employee.
On appeal from the Board’s decision, the Secretary had authority to reject or modify the penalty recommended by the Board. See id. In Ward’s letter of appeal he averred that the Board’s proposed penalty was inconsistent with the penalties imposed on other Department employees against whom a charge of patient abuse had been sustained, referring to the ALJ’s opinion, which was before the Secretary. Although Ward’s letter did not specifically cite the VA Manual, its discussion of disparate application of penalties was sufficient to alert the Secretary to *522the Board’s error. Further, plaintiffs neglect in citing the VA Manual is quite understandable in view of the Board’s failure to provide him with a copy of its regulations. Had the Secretary considered the issue, it could have rendered harmless the Board’s failure to address the policy of like penalties for like offenses in deciding on the disciplinary action to be taken against Ward.
After careful review of the administrative record, we see nothing to suggest the Secretary addressed the Board’s error. The Option Paper prepared and submitted to the Secretary by his legal staff characterized Ward’s claim only as a challenge to the Board’s application of the Douglas factors, concluding that the Board was not required to consider the Douglas factors, and that in any event mitigation of the proposed penalty was not warranted. There is no reference in the Option Paper to the VA policies, found in Pt. II, ch. 8, sec. C of the VA Manual, concerning disciplinary actions against full-time Department nurses. Instead, the Option Paper only refers to a Department Supplement to Part I of the VA Manual, the scope of which explicitly excludes nurses covered by the provisions of Part II. See VA Manual, MP-5, Pt. I, ch. 752, Change 2, ¶ 1(a) (Sept. 16, 1974). Further, the Secretary’s letter to Ward in response to Ward’s letter of appeal simply points out that the Secretary was sustaining the Chief Medical Director’s decision, who in turn had adopted the findings and recommendation of the Board.
In our view the Secretary’s acceptance of the proposed penalty of discharge was arbitrary and capricious because at no time during the administrative process was the Secretary’s own policy of like penalties for like offenses, promulgated under authority of 38 U.S.C. § 7462(d), ever addressed. Government agencies must take great care to follow their own rules and regulations. See Blassingame, 866 F.2d at 560. Here, the agency’s failure to follow or consider the regulations promulgated by the Secretary under § 7462 violated the APA. We therefore agree with the district court’s conclusion, although for slightly different reasons, that the Secretary’s decision regarding the penalty must be vacated as arbitrary and capricious.
In reaching this result, we reject appellants’ argument that the Secretary was not required to consider the penalties imposed upon other Department employees because evidence of such other disciplinary actions was not before the Board. The policy of like penalties for like offenses is one the Board was required to consider before recommending a penalty. See 38 U.S.C. § 4110(d); VA Manual, MP-5, Pt. II, ch. 8, sec. C-l. Since the Board failed to consider this policy when imposing in this case its heaviest penalty, it was incumbent on the Secretary to do so, in order to ensure that its decision — which is the final decision in such a proceeding — was made in accordance with VA rules and regulations. The Secretary may not justify his failure to provide Ward with meaningful review by relying on the fact that Ward did not bring to the Board’s attention records that the Board itself had a duty to consider.
B. The Remand
We turn finally to the remand issue. The Supreme Court has cautioned that when an agency has not considered all relevant factors in taking action, or has provided an insufficient explanation for its action, the appropriate course for a reviewing court ordinarily is to remand the case to the agency. See Florida Power & Light Co. v. Lorion, 470 U.S. 729, 744, 105 S.Ct. 1598, 1607, 84 L.Ed.2d 643 (1985). We therefore modify the district court’s order to the extent that it undertook to determine whether Ward’s discharge was consistent with the VA policy of like penalties for like offenses. On remand the Secretary shall himself determine whether discharging Ward would be consistent with the penalties imposed upon other Department employees, or the Secretary may send the case back to the Board for a determination of this issue. The Secretary shall also determine whether the policy of like penalties for like offenses is meant to be applied on a facility-by-facility basis, or on a system-wide basis. It may well be that depriving Ward of his employment was motivated by extraneous factors, a matter the *523administrative deeision-maker should determine. In either ease, the burden is on the agency to show that the action taken is in compliance with the statutes and regulations applicable to the VA. See Blassingame, 866 F.2d at 560; Camp v. Pitts, 411 U.S. 138, 143, 93 S.Ct. 1241, 1244, 36 L.Ed.2d 106 (1973) (per curiam). We do nothing to interfere with the district court’s retention of this case after the administrative process has run its course.
CONCLUSION
The district court’s order vacating the Secretary’s decision with respect to the penalty imposed is affirmed, and the case is remanded to the Secretary for further proceedings consistent with this opinion.
. My object all sublime
I shall achieve in time,
To let the punishment fit the crime,
The punishment fit the crime.
W. Gilbert & A. Sullivan, My Object All Sublime, in A Treasury of Gilbert and Sullivan 284 (Simon & Shuster eds., 1941).
. This section was repealed by Pub.L. 102-40, 105 Stat. 210 (1991), as part of a complete revision of chapter 73 of title 38. Similar provisions are recodified at 38 U.S.C. §§ 7461-7464 (Supp. Ill 1991).