Lorenzo Sanchez-Juarez pled guilty to one count of illegal reentry by a deported alien after conviction of an aggravated felony, in violation of 8 U.S.C. § 1326(a)(1), (a)(2), and (b)(2), and one count of aggravated identity theft, in violation of 18 U.S.C. § 1028A. He was sentenced to 65 months’ imprisonment, followed by two years of unsupervised release. He appeals his sentence, and the government challenges the appeal on jurisdictional grounds. For the reasons set forth below, we reject the government’s jurisdictional argument and remand for resentencing.1
*1111BACKGROUND
Mr. Sanchez-Juarez, a citizen of Mexico, was convicted in 2002 of transporting illegal aliens. He was sentenced to 194 days’ imprisonment, which amounted to time served, and he was immediately deported.
After returning to the United States, Mr. Sanchez-Juarez was detained by Bureau of Immigration and Customs Enforcement agents in August 2004 at a bus station and was found in possession of five fraudulent temporary permanent resident alien cards together with five Social Security cards. Upon learning of Mr. Sanchez-Juarez’s prior deportation, the agents placed him under arrest.
Mr. Sanchez-Juarez pled guilty, and the United States Probation Office prepared a presentence report (“PSR”), calculating a sentencing range based on the United States Sentencing Commission, Guidelines Manual (Nov.2004) (“USSG”). The PSR set the base offense level for count one, the illegal reentry offense, at 8, pursuant to USSG § 2L1.2(a). The PSR applied a 16-level enhancement pursuant to USSG § 2L1.2(b)(l)(A)(vii), based on Mr. Sanchez-Juarez’s prior deportation in 2002 following an alien smuggling offense. The PSR described this offense, noting that Border Patrol agents had initially observed Mr. Sanchez-Juarez driving a van with passengers on a New Mexico highway and discovered the van’s license plates belonged to another vehicle. The description continued:
Agents activated their lights and sirens on their vehicle in an attempt to stop the van, however, [Mr. Sanchez-Juarez] initially continued driving without yielding for approximately six miles down the road. Once the agents made contact with the passengers they learned that all were illegal aliens and citizens from the Republic of Mexico. Further questioning of the passengers revealed that [Mr. Sanchez-Juarez] had offered to take them to the United States if they would give him $900.00 to purchase a vehicle. Five of the illegal aliens reported that they contributed different amounts of money to give.to [Mr. Sanchez-Juarez] so he could purchase the vehicle. They crossed into the United States and [Mr. Sanchez-Juarez] met them at a previously arranged location on the United States side of the border.
PSR ¶ 20, R. Vol. II. As indicated, Mr. Sanchez-Juarez was sentenced to 194 days’ imprisonment time served for this offense.
The PSR then applied a three-level reduction for acceptance of responsibility, leading to a total offense level of 21. Together with a criminal history category of II, this yielded an advisory Guidelines range of 41 to 51 months’ imprisonment. The PSR then noted that Mr. Sanchez-Juarez’s conviction on count two, the aggravated identity theft offense, would require the imposition of a two-year term of imprisonment pursuant to 18 U.S.C. § 1028A(b)(2), to run consecutive to any other term of imprisonment. The PSR went on to describe a number of Mr. Sanchez-Juarez’s personal characteristics, including his family history, family ties, physical and mental condition, education, and employment history, and concluded that Mr. Sanchez-Juarez “does not appear to have any circumstances that would take him away from the heartland of cases of similarly situated defendants.” PSR ¶ 41, R. Yol. II. The PSR made no recommendation regarding what sentence the probation office would consider reasonable.
On August 19, 2005, Mr. Sanchez-Juarez filed a Motion for a Reasonable and Just Sentence and Sentencing Memorandum, in which he argued “for a lower sentence than the advisory guideline imprisonment range.” Mem. at 1, R. Yol. I, doc. 22. At *1112the sentencing hearing, held September 7, 2005, the district court indicated that it had not received Mr. Sanchez-Juarez’s memorandum but asked Mr. Sanchez-Juarez’s counsel to tell him what the memorandum said. Through counsel, Mr. Sanchez-Juarez argued that his prior alien smuggling conviction, for which he had been sentenced to only 194 days time served, “is in sharp contrast to the usual defendant convicted of reentry after deportation[,] ... [who][t]ypically ... have convictions for crimes of violence or for repeated serious drug offenses.” Tr. of Sentencing at 3, R. Vol. IV. He indicated that a number of courts “in reentry cases ... have been granting lower levels based on the relatively minor nature of the prior aggravated felony.” Id. at 5.
As a second reason for granting a below-Guidelines sentence, Mr. Sanchez-Juarez cited “exceptional family circumstances” in that he had been supporting a wife and two minor children. Id. at 6. Third, he indicated that “a deportable alien faces more severe restrictions in prison than a non-alien citizen.” Id. Fourth, he pointed to the sentencing disparity caused by the existence of “fast-track” programs in some jurisdictions, which provide for reduced sentences in illegal reentry cases where a defendant pleads guilty. He concluded that, based on the totality of these circumstances, the appropriate sentence on count one was below the 41- to 51-month Guidelines range.
In opposition, the government argued that a sentence between 41 and 51 months for count one was reasonable because “there is nothing atypical about this defendant’s background.” Id. at 8. In particular, the government argued that Mr. Sanchez-Juarez’s prior alien transporting conviction was squarely addressed by the Guidelines in USSG § 2L1.2(b)(l)(A)(vii), and “[if] they felt that it was important enough to give it [a 16-level enhancement], ... it’s that serious.” Tr. of Sentencing at 9, R. Vol. IV. The government also argued that Mr. Sanchez-Juarez’s family situation was “not atypical,” since many defendants “have a wife who is dependent, who [they are] trying to support, who has kids that the defendant is trying to provide food for.” Id.
Following these arguments, the court stated as follows:
The Court has reviewed the [PSR’s] factual findings and has considered the sentencing guideline applications.
The Court notes [Mr. Sanchez^Juarez] reentered the United States subsequent to an aggravated felony conviction. It is also noted [Mr. Sanchez-Juarez] possessed without lawful authority five Social Security cards in the names of five other persons.
Id. at 9-10. The court then sentenced Mr. Sanchez-Juarez to 41 months on count one, and the mandatory two years on count two, a total of 65 months.
Mr. Sanchez-Juarez appealed, arguing that the district court erred by failing to state reasons for the sentence it imposed and that his sentence was unreasonable in light of the sentencing factors set forth in 18 U.S.C. § 3553(a). The government contests these assertions but argues that, in any case, we have no jurisdiction to hear Mr. Sanchez^Juarez’s appeal because his sentence falls within the Guidelines range.
DISCUSSION
I. Subject matter jurisdiction
As an initial matter, we must address the government’s assertion that we lack subject matter jurisdiction over this appeal because Mr. Sanchez-Juarez’s sentence is within the calculated Guidelines range, and he does not allege that the court erred in *1113its application of the Guidelines. According to the government, “a claim that a sentence within a correctly calculated guideline range is unreasonable is outside the ‘limited appellate review’ authorized by 18 U.S.C. § 3742(a).” Appellee’s Br. at 10 (quoting Mistretta v. United States, 488 U.S. 361, 368, 109 S.Ct. 647, 102 L.Ed.2d 714 (1989)).
We have since held, however, that we do have jurisdiction to review sentences that fall within the Guidelines range. United States v. Chavez-Diaz, 444 F.3d 1223, 2006 WL 1000811, at *5 (10th Cir. Apr.18, 2006). Because the government did not raise the jurisdictional issue in that case, we respond to the government’s arguments here.
Section 3742(a) provides for appellate review “of an otherwise final sentence if the sentence ... was imposed in violation of law.” 18 U.S.C. § 3742(a)(1). Prior to the Supreme Court’s decision in United States v. Booker, 543 U.S. 220, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005), declaring the Guidelines advisory rather than mandatory, courts generally held, based on their interpretation of the phrase “in violation of law,” that § 3742(a) “d[id] not authorize a defendant to appeal a sentence where the ground for appeal consists of a claim that the district court abused its discretion in refusing to depart” downward from the Guidelines range. United States v. Ruiz, 536 U.S. 622, 627, 122 S.Ct. 2450, 153 L.Ed.2d 586 (2002). The government suggests that, because Booker did not modify § 3742(a) in any way, any jurisdictional limitations recognized under that provision must still apply.
To a large extent, the government’s argument on this point is simply inapposite. As we recognized in Chavez-Diaz, the pre-Booker rule on which the government relies applied to appellate review of a district court’s discretionary decision not to depart upward or downward from a mandatory sentencing range based on the grounds set forth in 18 U.S.C. § 3553(b)(1) and USSG Ch. 5 Pt. K. See Chavez-Diaz, 2006 WL 1000811, at *5; United States v. Coddington, 118 F.3d 1439, 1441 (10th Cir.1997). After Booker, which excised § 3553(b)(1) from the Sentencing Reform Act, see Booker, 543 U.S. at 259, 125 S.Ct. 738,2 circuits are divided in regard to whether such Guidelines-based departures may still be granted or have become obsolete. Compare United States v. Vaughn, 433 F.3d 917, 923 (7th Cir.2006) (“[T]he concept of a discretionary departure — over which we previously had no jurisdiction— has been rendered obsolete in the post-Booker world.” (internal quotation omitted)), with United States v. McBride, 434 F.3d 470, 477 (6th Cir.2006) (“[W]e believe that Guideline departures are still a relevant consideration for determining the appropriate Guideline sentence. This Guideline sentence is then considered in the context of the [§ ] 3553(a) factors.”). This circuit has stated that “[w]e view a direct challenge to a district court’s discretionary decision not to depart downward as a challenge to the district court’s preliminary application of the guidelines (the first step under [United States v.] Kristl [, 437 F.3d 1050 (10th Cir.2006) (per curiam) ]), and this challenge ... remains unreviewable.” Chavez-Diaz, 2006 WL 1000811, at *5.
However, the different positions on that issue have had no bearing on circuits’ assessment of their post-Booker jurisdiction. This is because post -Booker sentences within the Guidelines range do not result simply from the district court’s determination that no departure is warranted under *111418 U.S.C. § 3553(b)(1) and USSG Ch. 5 Pt. K. Rather, after Booker, every sentence that a district court ultimately imposes must reflect its determination of what is reasonable in light of the same § 3553(a) factors, whether that sentence is within or outside the Guidelines range.
Accordingly, as five other circuits have concluded, unreasonable sentences, whether they fall within or outside the advisory Guidelines range, are “imposed in violation of law” and thus reviewable pursuant to § 3742(a)(1).3 In effect, then, the meaning of “in violation of law” in § 3742(a) “is ... broadened for sentences imposed after Booker.” Chavez-Diaz, 2006 WL 1000811, at *5. We note, furthermore, that the Supreme Court in Booker expressly directed appellate courts to review all sentences for reasonableness.4
We conclude that we have jurisdiction over this appeal. We therefore proceed to address Mr. Sanchez-Juarez’s claims, based on the standards that, since Booker, have become established in our circuit.
il. Review of Mr. Sanchez-Juarez’s sentence
Following Booker, “[w]e review sentences imposed by the district court for reasonableness.” United States v. Galarza-Payan, 441 F.3d 885, 887 (10th Cir.2006). In conducting this review, we consider whether the district court correctly applied the Guidelines and whether the ultimate sentence is reasonable in light of the factors set forth in' 18 U.S.C. § 3553(a). United States v. Kristl, 437 F.3d 1050, 1053-54 (10th Cir.2006) (per curiam). We have held that when a sentence falls within the properly-calculated Guidelines range, it is “ ‘entitled to a re-buttable presumption of reasonableness.’ ” Galarza-Payan, 441 F.3d at 889 (quoting Kristi, 437 F.3d at 1054).
As indicated above, Mr. Sanchez-Juarez does not challenge the district court’s application of the Guidelines. However, he argues that the presumption of reasonable*1115ness does not apply here, even though his sentence falls on the low end of the correctly-calculated Guidelines range, and that his sentence is procedurally unreasonable, because the district court failed to state reasons for the sentence it imposed and failed to consider his arguments that the § 3553(a) factors warranted a sentence below the applicable Guidelines range. Alternatively, he contends that even if we apply the presumption, his arguments are sufficient to rebut it.
There is no question that, in addition to guiding our reasonableness review on appeal, the sentencing factors set forth in 18 U.S.C. § 3553(a) must be considered by the district court itself when imposing a sentence. See 18 U.S.C. § 3553(a).5 Indeed, after Booker, these factors “have a new vitality in channeling the exercise of sentencing discretion.” United States v. Trajillo-Terrazas, 405 F.3d 814, 819 (10th Cir .2005).
As described above, Mr. Sanehez-Juarez argued at the district court’s sentencing hearing that a number of factors warranted a below-Guidelines range sentence in this case and asked the court to impose a lower sentence than that calculated in the PSR. The court allowed Mr. Sanchez-Juarez to make these arguments and allowed the government to rebut them. Its decision to impose a sentence at the low end of the Guidelines range may fairly be read as a functional rejection of Mr. Sanchez-Juarez’s arguments and a denial of his request for a below-Guidelines sentence. However, the court stated no reasons for the sentence it imposed, other than first noting that it had reviewed the PSR’s factual findings and considered the Guidelines applications, and then citing Mr. Sanchez-Juarez’s offense conduct. The record indicates that at no time during the sentencing hearing or when imposing the sentence did the district court refer to the § 3553(a) factors.6
Both before and after Booker, we have emphasized that “we will ‘not demand that the district court recite any magic words to show us that it fulfilled its responsibility to be mindful of the factors that Congress *1116has instructed it to consider.’ ” United States v. Mares, 441 F.3d 1152, 1161 (10th Cir.2006) (quoting United States v. Contreras-Martinez, 409 F.3d 1236, 1242 (10th Cir.2005)) (further quotation omitted); see also United States v. Rines, 419 F.3d 1104, 1107 (10th Cir.2005), cert. denied, — U.S. -, 126 S.Ct. 1089, 163 L.Ed.2d 905 (2006); United States v. Kelley, 359 F.3d 1302, 1305 (10th Cir.2004). However, this principle does not mean that we may simply presume the district court weighed a party’s arguments in light of the § 3553(a) factors where the record provides no indication that it did so and no clear explanation of the sentence imposed. See McBride, 434 F.3d at 476 n. 3 (noting “that a district court need not use ... magic words ... is not a license for district courts to sentence without developing a sufficient record for appellate courts to review”).
Before Booker, we addressed the district court’s obligation to consider § 3553(a) factors when exercising its discretion in regard to sentencing decisions that were, even then, not subject to mandatory Guidelines. We held that although “the district court is not obligated to expressly weigh on the record each of the factors set out in § 3553(a),” it must “state its reasons for imposing a given sentence.” United States v. Rose, 185 ,F-3d 1108, 1111 (10th Cir.1999) (internal quotation omitted); see also Kelley, 359 F.3d at 1305; United States v. Kravchuk, 335 F.3d 1147, 1159 (10th Cir.2003); United States v. Zanghi, 209 F.3d 1201, 1204-05 (10th Cir.2000). We explained that the statutory requirement set forth in 18 U.S.C. § 3553(c) imposed a greater burden on district courts where their sentencing decisions involved an exercise of discretion.7 In such cases, we stated, the court’s failure to give reasons for its decision would leave us “in a zone of speculation” on appellate review. Rose, 185 F.3d at 1112 (internal quotation omitted). We further stated that it is not “consistent with our appellate function” “simply to assume” what the district court’s reasons might be in such cases. Zanghi, 209 F.3d at 1205.
The Seventh Circuit has applied the same reasoning to its review of sentences imposed post -Booker, where the district court must similarly exercise its discretion in determining a reasonable sentence in light of the § 3553(a) factors. United States v. Cunningham, 429 F.3d 673, 679 (7th Cir.2005) (observing that “whenever a district judge is required to make a discretionary ruling that is subject to appellate review, we have to satisfy ourselves ... that he exercised his discretion, that is, that he considered the factors relevant to that exercise”). In Cunningham, although the district court had stated that it had considered the § 3553(a) factors, the appellate court held that its “rote statement” was insufficient when the court had “passed over in silence the principal argument made by the defendant even though the argument was not so weak as not to merit discussion.” Id.; see also Cooper, 437 F.3d at 329 (adopting Cunningham rule).
The government argues that the question of the adequacy of the district court’s explanation “ha[s] been rendered moot” by our decision in Kristl, 437 F.3d at 1054, *1117that a sentence within the Guidelines is entitled to a presumption of reasonableness. Appellee’s Br. at 22. However, we do not believe our recognition of a procedural requirement that a district court must state reasons for its rejection of a party’s nonfrivolous motion is incompatible with the presumption that a sentence is reasonable in a substantive sense.8 See McBride, 434 F.3d at 476 n. 3 (distinguishing “substantive and procedural components” of reasonableness review). The district court record remains important to our review even applying the presumption. A district court’s explanation will assist us in our determination of whether a party has successfully rebutted the presumption on appeal. Indeed, we must rely on the district court to resolve any factual disputes raised by the parties that are relevant to the § 3553(a) factors. See United States v. Dean, 414 F.3d 725, 730 (7th Cir.2005) (explaining that explicit factfind-ing is required “if ... contested facts are material to the judge’s' sentencing decision”). Moreover, the fact that there is inevitably a range of sentences that could be held reasonable means that our affir-mance of a sentence will necessarily defer, in effect, to the district court’s exercise of discretion in choosing a particular sentence within that range. That being the case, our appellate role encompasses a limited inquiry into whether the district court did in fact exercise its discretion based on the 3553(a) factors, particularly since we have recognized that the Guidelines, though they incorporate these factors to a large extent, will not address all relevant factors in every case. United States v. Serrata, 425 F.3d 886, 918-19 (10th Cir.2005).
We are therefore persuaded that our pre-Booker requirement that district courts provide sufficient reasons to allow meaningful appellate review of their discretionary sentencing decisions continues to apply in the post -Booker context. In particular, where a defendant has raised a nonfrivolous argument that the § 3553(a) factors warrant a below-Guidelines sentence and has expressly requested such a sentence, we must be able to discern from the record that “the sentencing judge [did] not rest on the guidelines alone, but ... considered] whether the guidelines sentence actually conforms, in the circumstances, to the statutory factors.” Cunningham, 429 F.3d at 676. But see id. at 678 (noting that “arguments clearly without merit can ... be passed over in silence”); see also Lopez-Flores, 2006 WL 1000810, at *4 (holding § 3553(c) requirement was satisfied by general reference to Guidelines where “the defendant has not raised any substantial contentions concerning non-Guidelines § 3553(a) factors” to which the district court was obligated to respond, where the defendant did not object below to the district court’s failure to state reasons for its sentence, and where the sentence was at the low end of the Guidelines range).
Here, the argument Mr. Sanchez-Juarez raised at sentencing, and reiterates on appeal, concerning the incongruity between the actual conduct involved in his prior alien smuggling conviction and the 16-level increase suggested by the Guidelines is not clearly meritless. District courts have imposed below-Guidelines sentences because of such incongruities in other cases. See, e.g., United States v. Aus*1118tin, 2006 WL 305462, at *8 (S.D.N.Y. Feb.6, 2006); United States v. Santos, 406 F.Supp.2d 320, 328 (S.D.N.Y.2005); United States v. Zapata-Trevino, 378 F.Supp.2d 1321, 1327 (D.N.M.2005); United States v. Galvez-Barrios, 355 F.Supp.2d 958, 963 (E.D.Wis.2005). Furthermore, this court has indicated, when remanding a case based on nonconstitutional Booker error, that where § 2L1.2 imposed a 16-level enhancement but the actual offense conduct was “relatively trivial,” there was a “reasonable probability” that a district court exercising its discretion in light of the § 3553(a) factors would impose a below-Guidelines sentence. Trujillo-Terrazas, 405 F.3d at 819.9
Having identified one argument that is not clearly meritless and was raised at sentencing, we need not consider whether Mr. Sanchez-Juarez’s other arguments might have merit. Rather, we remand to the district court with instructions to vacate Mr. Sanchez-Juarez’s sentence and to resentence Mr. Sanchez-Juarez after considering his request that he receive a sentence below the applicable Guidelines range. In doing so, we in no way intend to express an opinion in regard to what the ultimate sentence should or should not be.
CONCLUSION
For the foregoing reasons, we REMAND to the district court with instructions to VACATE Mr. Sanchez-Juarez’s sentence and to resentence him following a hearing.