The petitioners in these consolidated petitions for review challenge an order of the Federal Communications Commission (FCC) that sets forth the conditions under which wireline telecommunications carriers must transfer telephone numbei*s to wireless carriers. The petitioners argue that the FCC’s order is a legislative rule that requires notice and comment under the Administrative Procedure Act (APA), 5 U.S.C. § 553, and a regulatory flexibility analysis under the Regulatory Flexibility Act (RFA), 5 U.S.C. § 604. The FCC contends that its order is an interpretative; rule — a rule that merely interprets one of the FCC’s previous legislative rales — and hence is exempt from APA and RFA requirements.
We conclude that the order is a legislative rule because it constitutes a substantive change in a prior rule. Although this rendered the order subject to the APA’s notice-and-comment requirements, we find that the FCC effectively complied with those requirements (notwithstanding its view that it was not required to do so), and that any deviations were at most harmless error. There is no dispute, however, that the FCC failed to comply with the RFA’s requirement to prepare a final regulatory flexibility analysis regarding the order’s impact.on small entities.
In light of these conclusions, we grant, the petitions in part and deny them in part, remanding the order to the FCC to prepare a final regulatory flexibility analysis. Until that analysis is complete, we stay the effect of the order solely as it applies to those carriers that qualify as small entities under the RFA.
I
The Telecommunications Act of 1996 imposes numerous duties on local exchange carriers (LECs), which, for purposes of this case, are wireline carriers — companies that provide telephone service over telephone wires. See 47 U.S.C. § 153(26) (defining LECs); see also FCC Br. at 2. The duty at issue here is the obligation “to provide, to the extent technically feasible, *151number portability in accordance with requirements prescribed by the Commission.” 47 U.S.C. § 251(b)(2). The Act defines “number portability” as “the ability of users of telecommunications services to retain, at the same location, existing telecommunications numbers without impairment of quality, reliability, or convenience when switching from one telecommunications carrier to another.” Id. § 158(30). The Act further directs the FCC “to establish regulations to implement” the statutory requirements. Id. § 251(d)(1).
On July 2, 1996, shortly after the 1996 Telecommunications Act became law, the FCC released its first order regarding number portability. See First Report and Order and Further Notice of Proposed Rulemaking, Telephone Number Portability, 11 F.C.C.R. 8352 (1996) (First Order). The First Order was issued pursuant to APA notice-and-comment procedures, and contained the regulatory flexibility analysis required by the RFA. Id. ¶ 1, at 8353-54, app. C, at 8486. In the First Order, the FCC recognized two kinds of portability that are relevant to this case: “service provider portability” and “location portability.” Id. ¶¶ 172, 174, at 8443.
The First Order required all carriers to provide service provider portability, which it made “synonymous with” the statutory definition of number portability: “the ability of users of telecommunications services to retain, at the same location, existing telecommunications numbers ... when switching from one telecommunications carrier to another.” Id. ¶ 27, at 8366-67. Compare 47 C.F.R. § 52.21(q), with 47 U.S.C. § 153(30). In addition, the First Order clarified that the portability obligation included not only porting between wireline carriers, but also “intermodal portability”: the porting of numbers from wireline carriers to wireless providers, and vice versa. First Order 11152, 11 F.C.C.R. at 8431, ¶ 155, at 8433, ¶ 166, at 8440; see 47 C.F.R. §§ 52.23(b), 52.31(a).1
Although the First Order mandated service provider portability, it expressly declined to require “location portability,” which it defined as “the ability of users of telecommunications services to retain existing telecommunications numbers ... when moving from one physical location to another.” First Order ¶ 174, 11 F.C.C.R. at 8443; see id. ¶6, at 8356; 47 C.F.R. § 52.21(j). But the First Order left many issues unresolved. In particular, while it required porting “at the same location,” and expressly declined to require porting when moving from “one physical location to another,” it did not define the word “location.”
The FCC enlisted a federal advisory-committee, the North American Numbering Council (NANC), to make recommendations regarding the implementation of number portability. See First Order ¶¶ 94-95, 11 F.C.C.R. at 8401-02. The FCC also established a phased schedule requiring LECs to complete implementation of number portability in the 100 largest metropolitan areas by December 31, 1998. See id. ¶ 77, at 8393. As a result of subsequent postponements, the carriers’ intermodal porting duty did not commence until November 24, 2003 in large metropolitan areas, and until six months later in other areas. See Verizon Wireless’ Petition for Partial Forbearance from the *152Commercial Mobile Radio Services Number Portability Obligation ¶ 31, 17 F.C.C.R. 14,972, 14,985-86, ¶ 34, at 14,986-87 (2002).
In 1997, the FCC received the NANC’s recommendations regarding wireline-towireline service provider portability and issued a second order that adopted those recommendations. See Second Report and Order, Telephone Number Portability, 12 F.C.C.R. 12,281 (1997) (Second Order); 47 C.F.R. § 52.26(a) (codifying the NANC Working Group Report). Like the First Order; the Second Order was issued pursuant to notice and comment and included a regulatory flexibility analysis. Second Order ¶ 2, 12 F.C.C.R. at 12,283, app. C, at 12,358. Under the Second Order, wirelineto-wireline number portability was “limited to carriers with facilities or numbering resources in the same rate center ....” See Memorandum Opinion and Order and Further Notice of Proposed Rulemaking, Telephone Number Portability; CTIA Petitions for Declaratory Ruling on Wire-line-Wireless Porting Issues ¶ 7, 18 F.C.C.R. 23,697, 23,700 (2003) {Intermodal Order) (citing the Second Order’s adoption of the NANC recommendations). Accordingly, a subscriber could not keep the same telephone number if he changed from a wireline telephone in one rate center to a wireline telephone physically located in a different rate center. Id. ¶ 7, at 23,700, ¶ 24, at 23,707. A “rate center” is a relatively small geographic area, designated by a LEC and state regulators, that is used to determine whether a given call is local or toll. See FCC, FCC Clears Way for Local Number Portability Between Wireline and Wireless Cartiers, 2003 WL 22658210 (Nov. 10, 2003); FCC Br. at 6-7.
The Second Order was limited to wire-line-to-wireline portability and did not resolve any issues relating to intermodal portability. Instead, the FCC once again enlisted the NANC to develop standards necessary to provide for wireless carriers’ participation in number portability. See Second Order ¶ 91, 12 F.C.C.R. at 12,333. In particular, the FCC asked the NANC to consider “how to account for differences between service area boundaries for wire-line versus wireless services.” Id. ¶ 91, at 12,334. (The “service area” of a wireless carrier is typically considerably larger than the rate center of a LEC. See FCC Br. at 7.) But the NANC was unable to reach a consensus on intermodal portability issues, especially because of the problem of “rate center disparity”:
[B]ecause wireline service is fixed to a specific location the subscriber’s telephone number is limited to use within the rate center within which it is assigned. By contrast, ... because wireless service is mobile ..., while the wireless subscriber’s number is associated with a specific geographic rate center, the wireless service is not limited to use within that rate center.
Intermodal Order ¶ 11, 18 F.C.C.R. at 23,-701 (discussing NANC Report).
On January 23, 2003, the Cellular Telecommunications & Internet Association (CTIA) petitioned the FCC for a declaratory ruling that “wireline carriers have an obligation to port their customers’ telephone numbers to a [wireless] provider whose service area overlaps the wireline carrier’s rate center” associated with the requested number. See Petition for Declaratory Ruling of the CTIA, Telephone Number Portability, CC Docket No. 95-116 (Jan. 23, 2003), at 1. CTIA asked the FCC to reject the view of certain LECs that portability was required only when a wireless provider had a physical presence in the wireline rate center from which the customer sought to port the number. Id. at 3. The FCC issued a public notice seeking comments on CTIA’s proposed rule. *153See Petition for Declaratory Ruling That Wireline Carriers Must Provide Portability to Wireless Carriers Operating Within Their Service Areas, 68 Fed.Reg. 7323 (Feb. 13, 2003). Numerous members of the wireline industry, including several of the petitioners here,2 submitted comments.
Some of the commenters argued that the FCC could not adopt the rule requested by CTIA without following APA rule-making procedures.3 Those commenters contended that intermodal porting, as proposed by CTIA, necessarily entails location portability because it requires LECs to port numbers to a wireless carrier even if the carrier has no facilities or assigned telephone numbers within the rate center associated with the number to be ported.4 Other commenters focused on the merits of the proposal. Those contended, inter alia, that CTIA’s proposal would give wireless carriers unfair advantages over wire-line carriers: while it would permit wireless carriers to port numbers from — and thus compete for — wireline customers, wireline carriers would be unable to compete for wireless customers whose numbers were outside the wireline carriers’ rate centers.5 Finally, some commenters contended that CTIA’s proposal would impose special burdens on small and rural telephone companies. They argued that, because wireless carriers rarely have switching capability within the service areas of small, independent wireline carriers serving small towns or rural areas, those wireline carriers would have to bear the costs of transporting calls outside their local service territories when their customers made calls to wireless subscribers with ported numbers.6
On November 10, 2003, the FCC released the order at issue in this case, known as the Intermodal Order. 18 F.C.C.R. 23,697 (2003). The Intermodal Order adopted the rule proposed in the CTIA petition. It requires wireline carriers to “port numbers to wireless carriers where the requesting wireless carrier’s ‘coverage area’ overlaps the geographic location of the rate center in which the customer’s wireline number is provisioned,” so long as “the porting-in carrier maintains the number’s original rate center designation following the port.” Id. ¶ 22, at 23,706. A wireless carrier’s “coverage area” is defined as the “area in which wireless service can be received from the wireless carrier.” Id. ¶ 1, at 23,698.7
*154The FCC insisted that the Intermodal Order had merely adopted “clarifications” of the wireline carriers’ existing obligation under prior orders, and hence did not require a new rulemaking. Id. ¶ 26, at 23,708. The Commission rejected the contention that it had imposed a duty of location portability. Because the number has to retain its original rate center designation, the FCC said, the number remains at the “same location” for purposes of the statutory and regulatory definitions of portability. Id. ¶ 28, at 23,708-09. The fact that the order requires wireline carriers to port numbers to wireless carriers that do not have “a physical point of interconnection or numbering resources in the rate center where the number is assigned” does not, according to the FCC, amount to location portability. Id. ¶ 1, at 23,698; see id. ¶ 26, at 23,708.
The U.S. Telecom Association and other entities, principally advancing the interests of wireline carriers, now petition for review of the Intermodal Order. They do not challenge the merits of the order. Rather, they contend that it is invalid solely because it is a legislative rule issued without adherence to the procedural requirements of the APA and RFA.8
II
The Administrative Procedure Act imposes notice-and-comment requirements (the specifics of which we discuss in Part III) that must be followed before a rule may be issued. See 5 U.S.C. § 553. The APA expressly states, however, that those procedural requirements do not apply to “interpretative rules.” See id. § 553(b).9 This court and many commentators have generally referred to the category of rules to which the notice-and-comment requirements do apply as “legislative rules.”10
The petitioners contend that the Inter-modal Order constitutes a legislative rule because it effectively amends the FCC’s previous legislative rule — the First Order. See, e.g., American Mining Cong. v. Mine Safety & Health Admin., 995 F.2d 1106, 1112 (D.C.Cir.1993) (stating that a rule that “effectively amends a prior legislative rule” is “a legislative, not an interpretative rule”).11 Our cases have formulated this “effective amendment” test in a number of ways. We have, for example, held that “new rules that work substantive changes,” Sprint Corp. v. FCC, 315 F.3d 369, 374 (D.C.Cir.2003) (emphasis added), *155or “major substantive legal addition[s],” Appalachian Power Co. v. EPA, 208 F.Bd 1015, 1024 (D.C.Cir.2000) (emphasis added), to prior regulations are subject to the APA’s procedures.12 Enunciating a similar test, the Supreme Court has said that if an agency adopts “a new position inconsistent with” an existing regulation, or effects “a substantive change in the regulation,” notice and comment are required. Shalala v. Guernsey Mem’l Hosp., 514 U.S. 87, 100, 115 S.Ct. 1232, 131 L.Ed.2d 106 (1995) (emphases added) (quotation marks omitted); see id. at 101, 115 S.Ct. 1232. Although these verbal formulations vary somewhat, their underlying principle is the same: fidelity to the rulemaking requirements of the APA bars courts from permitting agencies to avoid those requirements by calling a substantive regulatory change an interpretative rule. See Appalachian Power Co., 208 F.3d at 1024 (“An agency may not escape ... notice and comment requirements ... by labeling a major substantive legal addition to a rule a mere interpretation.”); C.F. Communications Corp. v. FCC, 128 F.3d 735, 739 (D.C.Cir.1997) (holding that the FCC “may not bypass [the APA’s notice-and-comment] procedure by rewriting its rules under the rubric of ‘interpretation’ ”).
We agree with the petitioners that the Intermodal Order effects a substantive change in the First Order. The First Order required carriers to ensure “the ability of users of telecommunications services to retain, at the same location, existing telecommunications numbers ... when switching from one telecommunications carrier to another.” First Order ¶ 27, 11 F.C.C.R. at 8366-67 (emphasis added); 47 C.F.R. § 52.21(q) (emphasis added). Although the First Order did not expressly define “same location,” the FCC did declare that it would not require “location portability,” which it defined as “the ability of users of telecommunications services to retain existing telecommunication numbers ... when moving from one physical location to another.” First Order ¶ 174, 11 F.C.C.R. at 8443 (emphasis added); see id. ¶ 6, at 8356; 47 C.F.R. § 52.21(j).
The Intermodal Order, by contrast, requires carriers to provide users with the ability to retain their existing numbers regardless of physical location. Under that order, a wireline carrier must port whenever “the requesting wireless carrier’s ‘coverage area’ overlaps the geographic location of the rate center in which the customer’s wireline number is provisioned,” provided that the porting-in carrier maintains the number’s original rate center designation. Intermodal Order ¶ 22, 18 F.C.C.R. at 23,706. Because wireless carriers’ coverage (service) areas are often quite expansive — in some cases encompassing much of the United States— the Intermodal Order effectively requires carriers to provide their subscribers with the ability to retain their numbers “when moving from one physical location to another,” notwithstanding the First Order’s declaration that such location portability would not be mandated.
Nor can the Intermodal Order derive support from the Second Order — another prior legislative rule, also issued pursuant to notice and comment. In the Second *156Order, which established the requirements for number portability in the wireline-towireline context, the FCC provided that such portability was “limited to carriers with facilities or numbering resources in the same rate center .... ” Intermodal Order ¶ 7, 18 F.C.C.R. at 23,700. But the Intermodal Order rejects a similar limitation for wireline-to-wireless' portability, and instead requires wireline carriers to port numbers to wireless carriers that do “not have a point of interconnection or numbering resources in the same rate center as the ported number ....” Id. ¶ 26, at 23,708; see id. ¶ 1, at 23,698 (describing a “point of interconnection” as something “physical”); In re StarNet, Inc., 355 F.3d 634, 638 (7th Cir.2004) (noting that “[u]sually a rate center corresponds to the group of customers (a subset of an area code) served by a given complement of telephone switching equipment”).
In short, the Intermodal Order requires wireline carriers to port telephone numbers without regard to the physical location of the subscriber, the equipment, or the carrier, and thus effectively requires location portability — a requirement that the First Order had foresworn. Under the Intermodal Order, a wireline subscriber can move from New York to California— 3000 miles from his original residence, from the wire attached to his original wire-line telephone, from the geographic boundaries of the original rate center, and from the original wireline company’s point of interconnection — and yet keep his telephone number provided that he switches to a wireless company with service overlapping the original rate center. Everything physical — the person, the residence, the telephone, the point of interconnection — is at a new location, yet porting is nonetheless required. Hence, by adopting the Intermodal Order, the FCC removed its prior “physical location” limitation on the duty to port.
The FCC makes three arguments in support of the contrary contention. First, it points to a single sentence in the First Order that, it maintains, provided notice of the interpretation later adopted in the Intermodal Order. That sentence, which comes directly after one that defines “location portability,” reads as follows: “Today, telephone subscribers must change their telephone numbers when they move outside the area served by their current central office.” First Order ¶ 174, 11 F.C.C.R. at 8443.
We do not see how this sentence provides support for the rule announced in the Intermodal Order. As the FCC concedes, the sentence described the FCC’s then-current rules — which did not require location portability. FCC Br. at 25. The sentence thus made clear that unless the Commission were to impose location portability — which it declined to do and insists it still has not done13 — subscribers would have to change their numbers if they moved outside the area served by them current carrier’s central office. Yet as we have discussed, under the Intermodal Order subscribers need not change their telephone numbers when they move outside the area served by their central office: instead, they can switch to a cell phone and retain the same number as long as they move anywhere in the wireless company’s overlapping sendee area — even across the country. Hence, the Intermodal Order permits the very outcome that the Commission associated with location portability. Moreover, because the ported number includes the subscriber’s original area code, this kind of portability exhibits a principal problem that the First Order associated with location portability: the *157“loss of geographic identity of one’s telephone number.” First Order ¶ 176, 11 F.C.C.R. at 8444.
This point is further driven home by examining the notice of proposed rulemaking that preceded the First Order. That notice contained the same sentence that would later appear- in the First Order. But it also contained a succeeding sentence that made the Commission’s meaning unmistakable by explaining what location portability would enable subscribers to do:
Today, telephone subscribers must change their telephone numbers when they move outside the area served by their current central office. Location portability would enable subscribers to keep their telephone numbers when they move to a new neighborhood, a nearby community, across the state, or even, potentially, across the country.
Notice of Proposed Rulemaking, Telephone Number Portability ¶ 26, 10 F.C.C.R. 12,350, 12,360 (1995) (emphasis added). And that is precisely what the Intermodal Order now enables subscribers to do.
Second, the FCC argues that “porting from a wireline to a wireless carrier that does not have a point of interconnection or numbering resources in the same rate center as the ported number does not, in and of itself, constitute location portability, because the rating of calls to the ported number stays the same.” Intermodal Order ¶ 28, 18 F.C.C.R. at 23,708 (emphasis added). The rating remains the same because the FCC added that requirement as a proviso: a wireline carrier must port to a wireless carrier if the latter’s service area overlaps the rate center associated with the subscriber’s number, “provided that the porting-in carrier maintains the number’s original rate center designation following the port.” Id. ¶ 22, at 23,706. The FCC insists that under this proviso, “the number does not leave the rate center,” and hence “it has not been subject to location porting.” FCC Br. at 25-26 (emphasis in original) (citing Intermodal Order ¶ 28).
But this focus on the “location” of the telephone number, based solely on its rating, is at best meta physical. It surely is not the physical location discussed in the First Order.14 Moreover, the First Order emphasized the user's location, not the number’s. See First Order ¶ 172, 11 F.C.C.R. at 8443 (defining location portability as “the ability of users ... to retain existing telecommunications numbers ... when moving from one physical location to another” (emphasis added)); id. ¶ 181, at 8447 (declaring that the “1996 Act’s requirement to provide number portability is limited to situations when users remain ‘at the same location’ ” (emphasis added)). Indeed, in the sentence highlighted by the FCC and discussed above, the First Order explained that in the absence of location portability, “subscribers must change their telephone numbers when they move outside the area served by their current central office.” Id. ¶ 174, at 8443 (emphases added).
Third, the FCC argues that the Inter-modal Order did not substantively change the First Order, but instead merely curtailed the unlimited portability requirement imposed in the First Order. The First Order, the FCC contends, “imposed no limitations on the LECs’ duty of wire-line-to-wireless porting.” FCC Br. at 20. And in the Commission’s view, the peti*158tioners have no reason to complain about a rule that merely reduced their preexisting obligations.
But it is simply wrong to say that the First Order “imposed no limitations” on a wireline carrier’s duty to port numbers to a wireless carrier. To the contrary, the order expressly limited that obligation by declaring that wireline carriers were not obligated to provide location portability. First Order ¶ 6, 11 F.C.C.R. at 8356. Accordingly, the petitioners have every reason to complain about a rule (if promulgated without notice and comment) that jettisoned the First Order’s promise regarding location portability.
Indeed, the FCC does not truly contend that the Intermodal Order would have been valid had it contained no limitation on the “unlimited” requirement of the First Order. Rather, as noted above, the FCC’s claim that the Intermodal Order does not impose location portability depends upon the order’s proviso that the porting-in carrier must maintain the number’s original rate center designation. Nor is that the only necessary limitation in the FCC’s view. The principal limit on portability announced by the Intermodal Order is that the wireless carrier’s coverage area must overlap the geographic rate center in which the customer’s wireline number is provisioned. And at oral argument, the FCC conceded that, had the Intermodal Order not included such a limit on the porting obligation, it “would have begun to be inconsistent with location poi’tability.” Oral Arg. Tape at 38:51-39:28. It is thus clear that the Intermodal Order cannot be defended as an interpretation that merely cuts back on an ostensibly unlimited portability obligation imposed by the First Order.
In short, this is not a case in which an interpretative rule merely “supplies crisper and more detailed lines than the authority being interpreted,” American Mining Cong., 995 F.2d at 1112, or simply provides “a clarification of an existing rule,” Sprint Corp., 315 F.3d at 374. Rather, it is one in which the rule at issue substantively changes a preexisting legislative rule. Such a rule is a legislative rule, and it can be valid only if it satisfies the notice-and-comment requirements of the APA.
There is another reason, specific to the 1996 Telecommunications Act, to regard the rule at issue here as legislative. The 1996 Act mandates number porting “in accordance with requirements prescribed by the Commission,” 47 U.S.C. § 251(b)(2), requirements that are to be “implement[ed]” in “regulations.” Id. § 251(d). As we explained in American Mining Congress, when a statute defines a duty in terms of agency regulations, those regulations are considered legislative rules. 995 F.2d at 1109.
Of course, even when a statute requires an agency to proceed by implementing regulations, it need not develop legislative rules to “address every conceivable question.” Shalala v. Guernsey Mem’l Hasp., 514 U.S. 87, 96, 115 S.Ct. 1232, 131 L.Ed.2d 106 (1995). But the question of what Congress meant by “at the same location” in its definition of number portability is not just any “conceivable question.” Rather, it is a crucial statutory element of the portability requirement itself, at least as far as wireline-to-wireless porting is concerned. Accordingly, the First Order did not satisfy the FCC’s statutory obligation to “establish regulations” to implement number portability when it merely required “service provider portability,” and then defined that phrase by parroting the definition of number portability already contained in the statute. See supra Part I; cf. Pearson v. Shalala, 164 F.3d 650, 660 (D.C.Cir.1999) (“[W]e are *159quite unimpressed with the government’s argument that the agency is justified in employing this standard without definition because Congress used the same standard .... ”). Something more was necessary,15 and that something was provided by the specifics of the wireline-to-wireless regulations contained in the Intermodal Order.
Finally, the FCC complains that technological disparities require a different interpretation of the statutory term “location” in the intermodal context than in the wire-line-to-wireline context, and that the Commission’s regulations should reflect that difference. The Commission may well be correct. We are not suggesting that the Intermodal Order is unreasonable; indeed, the petitioners do not challenge the substantive reasonableness of the rule. See Oral Arg. Tape at 1:02:06-1:02:13.16 It may be that, as a matter of telecommunications policy, “location” should have reduced significance in the wireline-to-wireless context, and that the FCC would be justified in defining the word without reference to anything “physical.”
But in declaring that it was not requiring location portability, and. in using the adjective “physical” in the definition of that term, the First Order made clear that it did regard location as a physical concept. Moreover, at least in the intermodal context, where one side of the porting transaction involves a wireline telephone, physical location is a quite meaningful concept.17 Accordingly, however physical location is measured — whether by the residence or geographic rate center of the wireline user, the coordinates of the land-line attached to the user’s telephone, or the point of interconnection of the user’s wireline carrier — a rule that requires the carrier to port the number to a wireless telephone that may be thousands of miles from any of those places represents a substantive change from the rule announced in the First Order.18 Such a change may be permissible, but to accomplish it the FCC must comply with the procedural requirements of the APA.19
*160For the foregoing reasons, we conclude that the Intermodal Order was a legislative rule, and that the FCC therefore had to issue it pursuant to the notice-and-eomment requirements of APA § 553. As the next Part explains, however, that is not the end of the story.
Ill
The Administrative Procedure Act requires that “[gjeneral notice of proposed rule making shall be published in the Federal Register,” 5 U.S.C. § 553(b); that “[ajfter notice required by this section, the agency shall give interested persons an opportunity to participate in the rule making through submission[s],” id. § 553(c); that “[ajfter consideration of the relevant matter presented, the agency shall incorporate in the rules adopted a concise general statement of their basis and purpose,” id.; and that a “substantive rule” shall be published “not less than 30 days before its effective date,” id. § 553(d). For the kind of informal rulemaking at issue here, no other procedures are required to satisfy the APA. See Vermont Yankee Nuclear Power Corp. v. NRDC, 435 U.S. 519, 524, 98 S.Ct. 1197, 55 L.Ed.2d 460 (1978).
Although the FCC does not raise the point, it appears that the Commission satisfied each of these requirements when it issued the Intermodal Order,20 The FCC published notice in the Federal Register. See 68 Fed.Reg. 7323.21 The notice sought comments on CTIA’s proposal “that wire-line carriers are obligated to provide portability of their customers’ telephone numbers to [wireless] providers whose service area overlaps the wireline carriers’ rate centers.” Id. The Commission received and considered comments on that proposal from, among others, the petitioners in this case. See supra note 2. It then adopted essentially the same rule proposed in the notice, in an order that explained the rule’s basis and purpose, and published that order. See 18 F.C.C.R. 23,697; see generally supra Part I.
The only deficiency in these procedures identified by the petitioners is that the FCC labeled its published notice as a request for comment on CTIA’s “Petition for Declaratory Ruling,” rather than as a “Notice of Proposed Rulemaking.”22 The label, however, is not fatal. As we held in New York State Commission on Cable Television v. FCC, “to remand solely because the Commission labeled the action a declaratory ruling would be to engage in an empty formality.” 749 F.2d 804, 815 (D.C.Cir.1984).
Nonetheless, because the FCC does not press it, we do not reach a final decision as to whether the procedures attending issuance of the Intermodal Order fully con*161formed to the APA. But we do address the question — raised in the petitioners’ own brief — of whether any procedural error that might have occurred was harmless. Pet’rs Br. at 17, 27-30; see 5 U.S.C. § 706 (requiring courts to take “due account” of “the rule of prejudicial error”). In making that assessment, the petitioners urge us to heed our admonition in Sprint Corp. v. FCC, that “an utter failure to comply with notice and comment cannot be considered harmless if there is any uncertainty at all as to the effect of that failure.” 315 F.3d 369, 376 (D.C.Cir.2003) (quoting Sugar Cane Growers Coop. v. Veneman, 289 F.3d 89, 96 (D.C.Cir.2002)). As we have just noted, however, there was no “utter failure” in this case; indeed, we are hard pressed to discern any failure at all.
In any event, we have no uncertainty that if there was a procedural failure, it was harmless. The petitioners contend that by “proceeding without issuing a notice, the FCC constrained the industry’s ability to propose solutions to technical and regulatory barriers to intermodal portability that would have enabled the FCC to proceed in a balanced, nondiscriminatory fashion.” Pet’rs Br. at 17. But unlike the situation in Sprint Corp., the FCC did not proceed without notice. To the contrary, the proposal published in the Federal Register made the issue under consideration crystal clear.23 And as we have said, the proposal was virtually identical to the order ultimately adopted by the Commission.
Nor did the FCC “constraint ] the industry’s ability to propose solutions.” Id. Again to the contrary, the Commission invited and received comment from the industry on intermodal portability. Nor was the industry misled by the fact that the notice was labeled a request for comment on CTIA’s petition for a declaratory ruling, rather than as a notice of proposed rulemaking. Indeed, as the petitioners conceded at oral argument, every challenge to the Intermodal Order that they have raised in their appellate briefs was also made during the comment period. Oral Arg. Tape at 19:33-19:42.24 And they cannot identify a single additional comment that they would have made but for the labeling of the notice, nor any other deficiency in the rulemaking process. Id.; see New York State Comm’n, 749 F.2d at 815 (declining to remand an FCC order, despite a claim that the notice was mislabeled, where the “arguments raised in” the comments were “identical to the issues on appeal”).25
Under these circumstances, any error— if error there was — -was plainly harmless. *162Accordingly, although we conclude that the Intermodal Order was a legislative rule requiring adherence to the procedures specified in APA § 553, we find no deficiency in the procedures actually followed that would warrant vacating or remanding the order.26
IV
The Regulatory Flexibility Act also imposes procedural requirements on agency rulemaking, in particular the preparation of a “final regulatory flexibility analysis” regarding the effect of the rule on small businesses. See 5 U.S.C. § 604.27 That requirement applies “[w]hen an agency promulgates a final rule under section 553 of this title, after being required by that section or any other law to publish a general notice of proposed rulemaking.” Id. Because we have concluded that the FCC was required by section 553 to publish such a notice, the RFA’s requirements are applicable to the Intermodal Order.
By contrast to the notice-and-comment requirements, there is no dispute that the FCC utterly failed to follow the RFA when .it- issued the Intermodal Order. Nor is there an argument that the Commission’s failure was harmless, as it is impossible to determine whether a final regulatory flexibility analysis — which must include an explanation for the rejection of alternatives designed to minimize significant economic impact on small entities, see id. § 604(a)(3) — would have affected the final-order when it was never prepared in the first place. See Sprint Corp., 315 F.3d at 377 (holding that the wholesale failure to afford proper notice and comment was not harmless because “the effect of the Commission’s procedural errors is uncertain”).
The RFA outlines the remedies available for its violation as follows:
In granting any relief in an action under this section, the court shall order the agency to take corrective action ... including, but not limited to—
(A) remanding the rule to the agency, and
(B) deferring the enforcement of the rule against small entities unless the court finds that continued enforcement of the rule is in the public interest.
Id. § 611(a)(4). A combination of the two specified remedies — remand coupled with a stay of enforcement against small entities — is appropriate here.
, The petitioners contend that the order will have a serious impact on small rural carriers, which will have to impose the initial cost of implementation and the continuing cost of transporting calls to ported numbers on a narrow base of rural subscribers. Those costs, the petitioners argue, “bring[ ] no benefit to the vast majority of rural subscribers that are unwilling to give up their wireline service, yet must bear the cost burden nonetheless.” Pet’rs Br. at 18. The petitioners do not seek to undo any porting of numbers that has already occurred; they ask only to stay *163the mandatory obligation to accede to new porting requests. Oral Arg. Tape at 57:15-57:55.
The FCC does not contest the petitioners’ argument, and it gives no reasons why continued enforcement of the order with respect to small entities pending a final regulatory flexibility analysis would be in the public interest.28 Rather, it stands on its contention that no regulatory flexibility analysis was required at all. See FCC Br. at 30. Under these circumstances, we have no basis for finding that continued enforcement against statutorily defined small entities during the remand would be in the public interest.
Accordingly, we remand the Intermodal Order to the FCC for the Commission to prepare the required, final regulatory flexibility analysis. We stay future enforcement of the Intermodal Order only as applied to carriers that qualify as small entities under the RFA. The stay will remain in effect until the FCC completes its final regulatory flexibility analysis and publishes it in accordance with 5 U.S.C. § 604(b). Of course, nothing in this disposition prevents small carriers from voluntarily adhering to the Intermodal Order’s number portability requirements during that period.
V
For the foregoing reasons, we deny the petitions with respect to the APA claim, and grant the petitions with respect to the RFA claim. We remand the Intermodal Order to the FCC for the purpose of preparing a final regulatory flexibility analysis, and we stay future enforcement of the order against carriers that are “small entities” under the RFA until the FCC prepares and publishes that analysis.
So ordered.
. The First Order also required porting between wireless providers. First Order ¶ 155, 11 F.C.C.R. at 8433. Although the Telecommunications Act of 1996 imposed porting duties only on LECs, the FCC relied on another statute, the Telecommunications Act of 1934, as the basis for imposing a porting obligation on wireless carriers. Id. ¶ 4, at 8355, ¶ 153, at 8431 (relying on the FCC's authority over the wireless spectrum, as described in 47 U.S.C. § 332).
. See, e.g., Comments of the U.S. Telecom Ass'n, Telephone Number Portability, CC Docket No. 95-116 (Feb. 26, 2003); Comments of the Organization for the Promotion and Advancement of Small Telecommunications Companies, Telephone Number Portability, CC Docket No. 95-116 (Feb. 26, 2003).
. See, e.g., Ex Parte Letter from M.T. McMenamin, USTA, to M.H. Dortch, FCC, Telephone Number Portability, CC Docket No. 95-116 (Sept. 30, 2003); Ex Parte Letter from K.B. Levitz, BellSouth, to M.H. Dortch, FCC, Telephone Number Portability, CC Docket No. 95-116 (Sept. 30, 2003).
. See Ex Parte Letter of M.T. McMenamin, supra; Ex Parte Letter of K.B. Levitz, supra.
. See Ex Parte Letter from C. O'Connell, Qwest, to M.H. Dortch, FCC, Telephone Number Portability, CC Docket No. 95-116 (Oct. 17, 2003).
. See Comments of the Organization for the Promotion and Advancement of Small Telecommunications Companies, supra.
. The order also required wireless carriers to port numbers to wireline carriers, but only to wireline carriers within a number's originating rate center. Moreover, “because of the limitations on wireline carriers' networks ability to port-in numbers from distant rate centers,” the FCC said it would "hold neither the wireline nor the wireless carriers liable for failing to port under' these conditions,” but would instead issue a further notice of *154proposed rulemaking on the issue. Intermodal Order ¶ 22, at 23,706.
. On May 13, 2003, CTIA filed a separate petition with the FCC regarding wireless-to-wireless porting. The FCC issued an order resolving that petition on October 7, 2003. See Telephone Number Portability — Carrier Requests for Clarification of Wireless-Wireless Porting Issues, 18 F.C.C.R. 20,971 (2003). That order is the subject of another set of petitions for review in this court, which were argued on the same day as the present case.See Central Tex. Tel. Coop., Inc. v. FCC, No. 03-1405, 2005 WL 562741, 402 F.3d 205 (D.C.Cir. Mar. 11, 2005).
. Although the APA's notice-and-comment procedures are also inapplicable to certain "adjudication[s]," the FCC made it clear that it regards the Intermodal Order as a rule rather than an adjudication. See FCC Br. at 18; Oral Arg. Tape at 30:02-30:35.
. See, e.g., Appalachian Power Co. v. EPA, 208 F.3d 1015, 1020 & n. 11 (D.C.Cir.2000); Richard J. Pierce, Jr., I Administrative Law Treatise § 6.1, at 304 (2002); John F. Manning, Nonlegislative Rules, 72 Geo. Wash. L. Rev. 893, 893 (2004).
. See also Sprint Corp. v. FCC, 315 F.3d 369, 374 (D.C.Cir.2003) (noting that "an amendment to a legislative rule must itself be legislative" (quotation marks omitted)); National Family Planning & Reprod. Health Ass’n v. Sullivan, 979 F.2d 227, 235 (D.C.Cir.1992) (same).
. See also Alaska Prof'l Hunters Ass’n v. FAA, 177 F.3d 1030, 1034 (D.C.Cir.1999) (“[W]hen an agency has given its regulation a definitive interpretation, and later significantly revises that interpretation, the agency has in effect amended its rule, something it may not accomplish without notice and comment.”); American Mining Cong., 995 F.2d at 1109 (”[I]f a second rule repudiates or is irreconcilable with [a prior legislative rule], the second rule must be an amendment of the first (quotation mark omitted) (second alteration in original)).
. See Intermodal Order ¶ 28, 11 F.C.C.R. at 23,708-09; FCC Br. at 5.
. Indeed, at oral argument in the companion case, which concerned the FCC's order on wireless-to-wireless porting, see supra note 8, FCC counsel conceded that to say a number is ''located” within its rale center is "almost a bit of fiction; there really is no physical location ...Central Tex. Tel. Coop., Inc. v. FCC, No. 03-1405, Oral Arg. Tape at 32:05-32:28.
. As discussed above, to the extent that the First Order did do something more than parrot the statutory definition (e.g., by inserting the reference to “physical” location), it did so in language that is inconsistent with the Inter-modal Order.
. The petitioners do contend that the Inter-modal Order represents a significant departure from the First Order's promise that the FCC would maintain competitive neutrality between wireline and wireless carriers. The petitioners do not, however, contend that this asserted departure renders the Intermodal Order substantively invalid, but only argue that it supports the proposition that the Intermodal Order is so different from the First Order that it cannot be an interpretative rule. Pet’rs Br. at 24; Oral Arg. Tape at 1:01:45-1:02:07. Because we conclude that the Intermodal Order is not an interpretative rule for other reasons, we do not consider this argument. For the same reason, we do not consider the intervenors’ argument that the Intermodal Order is a legislative rule because it assertedly changes interconnection obligations.
. This point distinguishes our analysis of the FCC’s Intermodal Order from our analysis of the Commission’s wireless-to-wireless order, as set forth in Central Tex. Tel. Coop., Inc. v. FCC, No. 03-1405, 2005 WL 562741, 402 F.3d 205 (D.C.Cir. Mar. 11, 2005).
. Cf. In re StarNet, Inc., 355 F.3d at 638 (noting that "[ljanguage in the regulations links ‘location portability’ to movement ‘from one physical location to another,’ but does not distinguish among the customer’s physical location, the end of the wire’s physical location, or the rate center’s physical location” (internal citation omitted)).
. Cf. C.F. Communications Corp., 128 F.3d at 739 (holding that, although the Commission may be able to "amend its rules to render ‘premises’ a term of art encompassing telephone equipment or land ... on which telephone equipment is located[,] ... to do so, it must use the notice and comment procedure of the Administrative Procedure Act”); Paralyzed Veterans of Am. v. D.C. Arena L.P., *160117 F.3d 579, 586 (D.C.Cir.1997) (“Once an agency gives its regulation an interpretation, it can only change that interpretation as it would formally modify the regulation itself: through the process of notice and comment rulemaking.”).
. At oral argument, the FCC explained that it did not press this point because APA compliance would not resolve the RFA issue. See Oral Arg. Tape at 26:30-26:40; see also infra Part IV.
. The APA requires that the notice include: "(1) a statement of the time, place, and nature of public rule making proceedings; (2) reference to the legal authority under which the rule is proposed; and (3) either the terms or substance of the proposed rule or a description of the subjects and issues involved." 5 U.S.C. § 553(b). The FCC's notice contained each of these elements.
.As mentioned supra note 9, despite the label the FCC does not defend the Intermodal Order on the ground that it was a "declaratory ruling” lhat constituted an adjudication under 5 U.S.C. § 554(e).
. Indeed, the title alone encapsulated the proposal under consideration: Petition for Declaratory Ruling That Wireline Carriers Must Provide Portability to Wireless Carriers Operating Within Their Service Areas, 18 F.C.C.R. 832 (2003).
. See, e.g., Intermodal Order ¶ 16, 18 F.C.C.R. at 23,703-04 (noting comments that the CTIA proposal could not be promulgated without notice-and-comment rulemaking, that it would give wireless carriers an unfair competitive advantage over wireline carriers, that it would amount to a system of location portability, and that it would cause particular difficulties for rural LECs); supra Part I and notes 2-6.
. The Intermodal Order differed in each respect noted in the preceding two paragraphs from the payphone provider rule at issue in Sprint Corp., 315 F.3d 369. In Sprint Corp., the notice that preceded issuance of the payphone rule was not published in the Federal Register and described a proposal completely different from that which the FCC ultimately adopted. Id. at 374, 376. Moreover, "the comments submitted in response to the ... Notice demonstrate^] that the parties did not appreciate that the Commission was contemplating" the rule it finally issued. Id. at 376.
. The petitioners also contend that the First Ordel and Second Order established a procedure for resolving number portability issues that required reference to the NANC. As a consequence, the petitioners maintain that until the NANC submits a proposal, the FCC may not impose a porting obligation without first engaging in APA rulemaking. Although we do not read the first two orders as establishing any such mandatory procedure, the contention is mooted by our conclusion that issuance of the Intermodal Order satisfied the APA.
. Although the RFA grants courts jurisdiction to review claims of noncompliance with the provision of the Act that requires preparation of a final regulatory flexibility analysis, 5 U.S.C. § 604, judicial review under other provisions of the RFA is limited, see 5 U.S.C. § 611(a).
. The FCC does allege that the public interest weighs against vacáting the entire rule (as to entities of every size), and that such a remedy would be overbroad given the injury claimed to rural carriers. FCC Br. at 36.