This venue case requires us to decide whether a convicted sex offender who violates 18 U.S.C. § 2250(a) when he (1) abandons his residence in one state, (2) moves from that state to another, and (3) knowingly fails to update his sex offender registration can be prosecuted in the state from which he departed. In other words, is venue proper in the departure district for the federal crime of knowingly failing to register as a sex offender after traveling in interstate commerce?
We find that it is, and, exercising jurisdiction under 28 U.S.C. § 1291, we AFFIRM the district court’s decision. Under the relevant statutory provisions and case law, a sex offender may be prosecuted in either the departure district where the offense began or in other districts where the offender was required to update his registration.
I. Background
In 1996, Marcus Lewis pleaded guilty to statutory rape in Missouri and was sentenced to five years of probation. He later *1088served prison time on account of a probation violation. As a convicted sex offender, Lewis was required by federal law to register his status in his state of residence under the federal Sex Offender Registration and Notification Act (SORNA) and its statutory predecessors. Lewis last registered in Kansas in May 2011, and he has not voluntarily registered in any other state since that time.
Congress enacted SORNA in 2006 to require convicted sex offenders to register where they live, work, or attend school. Any changes in status must be reported to authorities at any new place of residency. In this way, a national database is created and kept current, providing up-to-date information about the location and movement of covered sex offenders.
In August 2011, a sheriffs deputy for Lyon County, Kansas, tried to locate Lewis on a warrant for a probation violation unconnected to his sex offense. Accessing the sex offender registry, the deputy went to Lewis’s last known address, but learned that Lewis no longer lived there. Unable to locate Lewis, the deputy turned the matter over to the U.S. Marshals Service. The marshals, relying on information available in their database about Lewis’s family members, visited Kansas City, Missouri, in hopes of finding Lewis. The marshals could not physically locate Lewis at the Kansas City address, but did identify a car associated with him.
Almost a year later, on July 25, 2012, Lewis was apprehended in Atlanta, Georgia, on the Lyon County warrant. An Atlanta-based inspector for the marshals interviewed Lewis in the Fulton County jail, where Lewis admitted that he left Kansas because he worried his probation officer would report him for violations. During the interview, he also explained that he had first traveled to Missouri to visit relatives and later took a Greyhound bus to Georgia. When he arrived in Georgia, he stayed in a homeless shelter for six months, but had since become employed and made plans to marry. Finally, Lewis confessed he knew of his obligation to register in Georgia upon changing his residence, but that he resisted doing so for fear of being arrested on his outstanding Kansas warrants.
A federal grand jury in the District of Kansas indicted Lewis for one count of failing to register between August 2011 and July 2012 under 18 U.S.C. § 2250(a). Lewis filed a motion to dismiss for improper venue, claiming that the alleged violation did not occur in Kansas. The district court denied this motion.
After the government declined to agree to a conditional plea, the case proceeded to a stipulated bench trial, and the district court found Lewis guilty of violating § 2250(a). Following the trial, Lewis filed a motion for judgment of acquittal, which raised the improper venue issue and claimed that the evidence of venue was insufficient for conviction. The district court denied this motion and later sentenced Lewis to 24 months in prison.
II. Analysis
Lewis contends venue was improper in Kansas. Along these lines, he argues that SORNA requires him only to register either in Missouri or Georgia because he abandoned his home in Kansas, traveled through Missouri, and established residency in Georgia. According to Lewis, any SORNA violation occurred — and thus could only be prosecuted — in states other than Kansas.
Although venue is ordinarily a fact question, we review de novo a district court’s legal finding of sufficient evidence to support a venue determination. United States v. Kelly, 585 F.3d 1229, 1232 (10th *1089Cir.2008). We assess whether venue is proper in a particular district by determining whether, “viewing the evidence in the light most favorable to the Government and making all reasonable inferences and credibility choices in favor of the finder of fact, the Government proved by preponderance of direct or circumstantial evidence that the crimes charged occurred within the district.” United States v. Rinke, 778 F.2d 581, 584 (10th Cir.1985). “Our review is ‘quite deferential.’ ” Kelly, 535 F.3d at 1233 (quoting United States v. Evans, 318 F.3d 1011, 1021 (10th Cir. 2003)).
A. SORNA
The Sex Offender Registration and Notification Act, 42 U.S.C. § 16901 et seq., was established as part of a broad legislative scheme intended to protect the public from the dangers posed by persons convicted of sex crimes. To accomplish this end, SORNA contains both a civil registration provision and a criminal provision. Under the registration provision, SORNA requires that a convicted sex offender “register, and keep the registration current, in each jurisdiction where the offender resides, where the offender is an employee, and where the offender is a student.” 42 U.S.C. § 16913(a). Subsection (c) of § 16913 creates a reporting obligation pursuant to which an offender must appear in person in “at least 1 jurisdiction involved” to update his registration any time he changes, among other things, his residence. Id. § 16913(c).1
As an enforcement mechanism for § 16913’s registration requirements, § 2250 is SORNA’s criminal constituent and it subjects any person required to register under § 16913 and who “is a sex offender ... by reason of a conviction under Federal law” or “travels in interstate or foreign commerce” to fines or imprisonment in the event that he “knowingly fails to register or update a registration as required by [SORNA].” 18 U.S.C. § 2250(a); see also United States v. Yelloweagle, 643 F.3d 1275, 1278-79 (10th Cir. 2011).
The elements of a § 2250 violation are sequential, Carr v. United States, 560 U.S. 438, 456, 130 S.Ct. 2229, 176 L.Ed.2d 1152 (2010), and each must be proven beyond a reasonable doubt. In Lewis’s case, the government must establish that Lewis (1) was required to register under SORNA; (2) traveled in interstate commerce; and (3) knowingly failed to register or update his registration during the time period specified in the indictment. Lewis admits that the government can meet all three of the statute’s explicit elements, but contests whether the government has sufficient evidence to establish proper venue in Kansas.
To prove venue — which is a necessary, if often subtle, element of every criminal statute — the government must establish where the failure to register occurred by a preponderance of the evidence. And because § 2250 does not have a specific venue provision, venue is established using traditional statutory and common law tools to ascertain “the nature of the crime alleged and the location of the act or acts constituting it.” United States v. Medina-Ramos, 834 F.2d 874, 876 (10th Cir.1987) (quoting United States v. Anderson, 328 U.S. 699, 703, 66 S.Ct. 1213, 90 L.Ed. 1529 (1946)); see also United States v. Cryar, 232 F.3d 1318, 1321 (10th Cir.2000).
*1090 B. Venue
Although it is contested infrequently in criminal cases, establishing proper venue is a matter of constitutional significance.2 See Kelly, 535 F.3d at 1233. Paraphrasing the Constitution, the Federal Rules of Criminal Procedure require that prosecution must ensue in the district where the offense occurred, absent a statute or other procedure allowing for another venue. See Fed.R.Crim.P. 18. Lewis argues that his violation of § 2250 did not occur in Kansas because he was not required to register until he left the state and took up a new residence elsewhere. In other words, Lewis contends venue was improper in Kansas because he only consummated a SORNA violation when he moved to Missouri (and then to Georgia) and failed to update his registration in those states, which may have been proper venues. For several reasons, we disagree.
1. SORNA’s Reporting Obligation
The reporting obligation under § 16913(c) arises as soon as the offender abandons his former residence, even if he has yet to establish a new, permanent residence. United States v. Murphy, 664 F.3d 798, 801-02 (10th Cir.2011); see also United States v. Voice, 622 F.3d 870, 874-75 (8th Cir.2010). Thus, although SORNA grants a three-day grace period, the offender is required to report the change in status to at least one “jurisdiction involved” upon leaving his former residence. In many cases, the offender can satisfy his obligation by updating his registration in the new SORNA jurisdiction where he settles, as long as the registration takes place within three days of the abandonment of the prior residence. If it does not, then the offender “must register twice — within three days of abandoning his former residence, and within three days of establishing the new one.” Murphy, 664 F.3d at 803.
In Murphy, the government successfully prosecuted the defendant in the departure district, and we affirmed his conviction. And although in Murphy we did not reach the question posed here — namely, whether the § 2250 offense actually occurs in the departure district — the facts of Murphy are instructive. In that case, we were asked to determine whether a sex offender subject to SORNA violated the statute when he abandoned his domestic residence and moved abroad. Specifically, the sex offender left Utah and traveled to Belize via California and Mexico. Because SORNA does not apply extraterritorially, Belize could not be a “jurisdiction involved” under the statute. Although this international aspect of the case made Murphy's facts unusual, we found that the plain language of § 16913 obligated the defendant to update his registration in Utah, his departure district. Id. at 804. Importantly, the relevance of Murphy’s conclusion that the violation of SORNA took place in the departure district is the product of two independent, but harmonious, interpretations of SORNA’s statutory language.3
*1091First, in Murphy we acknowledged that “a ‘jurisdiction where the offender resides’ and a ‘residence’ are two different concepts. Identifying a jurisdiction involved implicates a different inquiry than deciding whether a reporting obligation has arisen.” Id. at 801. For this reason, we concluded that Murphy was required to update his registration in Utah when he abandoned his “residence”:
The record demonstrates Murphy knowingly violated SORNA by failing to update his registration. Although he had not yet established a new residence, Murphy changed his residence for SORNA purposes when he permanently left Bonneville. And although he was no longer residing at a particular location, Murphy’s reporting obligation did not end just because he left the state. As a result, a legal obligation to update his registration attached when he left Bonneville, while he was still in Utah, and not when he arrived in Belize.
Id. at 803-04.
The effect of Murphy’s holding is that the abandonment of a permanent residence triggers a sex offender’s obligation to update his registration.4 To be sure, a sex offender convicted under state law cannot be in technical violation of § 2250 until he moves in interstate commerce and then fails to register, but it is the abandonment of the residence that sets this sequence in motion. In this way, the abandonment activates the reporting obligation’s three-day timer and signifies the commencement of the offense. This logic necessarily permits venue to lie in the departure district.
Alternatively, Murphy holds that, for the purposes of § 16913, the departure district remains a “jurisdiction involved” even after the sex offender has left the state. “When an offender leaves a residence in a state, and then leaves the state entirely, that state remains a jurisdiction involved. Even if a sex offender plans on leaving a state permanently, his reporting obligation to a jurisdiction involved remains.” Murphy, 664 F.3d at 803. As a “jurisdiction involved,” the government can use the departure district as the venue for prosecuting his failure to register. Evidence that the sex offender never registered after leaving his original jurisdiction of residence is sufficient to prove that he violated the statute in the departure jurisdiction.
This is also the conclusion endorsed by the National Guidelines for Sex Offender Registration and Notification. See generally Office of the Attorney General, The National Guidelines for Sex Offender Registration and Notification, 73 Fed.Reg. 38030-01 (July 2, 2008). Those guidelines, on which the district court relied, establish that the district from which a sex offender departs — or abandons his residence — is still a “jurisdiction involved” under SORNA. See 42 U.S.C. § 16913; Attorney *1092General Guidelines, 73 Fed.Reg. at 38030-01. This is because even when the offender travels in interstate commerce and updates his status in a new district, the new district must provide notice to the former state of residence to fortify SORNA’s interconnected web of state registries. Thus, the defendant’s failure to update his registration has disrupted the intended seamless web of SORNA protection by not alerting all relevant jurisdictions of his whereabouts. The implication is that the departure jurisdiction may be a “jurisdiction involved” even after the sex offender has left. Attorney General Guidelines, 73 Fed.Reg. at 38030-01.
Lewis argues that Murphy is wrongly decided, and points to the Eighth Circuit’s recent decision in United States v. Lunsford, 725 F.3d 859 (8th Cir.2013), for support. In that case, the court concluded “that an offender who leaves a domestic jurisdiction for a foreign jurisdiction” need not “necessarily ... update his registration in the domestic jurisdiction where he formerly resided.” Id. at 862 (emphasis added). But on the venue issue, the Lunsford court did not dispute circuit precedent previously holding that a sex offender who departs from one SORNA jurisdiction to another without updating his registration in either jurisdiction may be prosecuted— that is, venue is proper — in the departure jurisdiction. See id. at 863 (citing United States v. Howell, 552 F.3d 709 (8th Cir. 2009)). Although Lunsford criticized Howell to the extent that it might be read to say that a sex offender is necessarily “required by [federal] law ... to notify the [departure district’s] offender registry of his move,” Howell, 552 F.3d at 718, Lunsford did not dispute Howell’s holding at least insofar as it found venue is proper in the departure jurisdiction where it is clear that the sex offender failed to register in any domestic jurisdiction. Lunsford, 725 F.3d at 863. And unlike Howell, our decision here does not establish a mandatory federal reporting obligation in the departure district — the offender could update his registration by contacting either the departure jurisdiction or the arrival jurisdiction; when he fails to do one or the other, he has violated the federal statute in both, and venue lies in either.
In sum, we find Murphy’s logic controlling because it establishes that a violation of § 2250 occurs in the departure district. After leaving Kansas and failing to register, Lewis was a fugitive subject to prosecution in Kansas because (1) abandoning his residence there triggered his reporting obligation, and (2) Kansas remained a “jurisdiction involved” under SORNA because he never registered in another jurisdiction.
2. Federal Venue Statute, 18 U.S.C. § 3237
Although venue was not an issue in Murphy, the conclusion that venue is proper in the departure district logically follows from Murphy’s holding that a SORNA violation was committed in the departure district. Indeed, in Murphy, we cited with approval cases from other circuits finding that “when a sex offender moves from one state to another without updating his registration, venue is proper in both jurisdictions, even though the defendant no longer resides in the former state.” Murphy, 664 F.3d at 802 n. 3 (citations omitted). Even the dissent in that case had no qualms with finding venue in the departure district. Id. at 807 (Lucero, J., dissenting) (“[T]he venue cases cited by the majority merely stand for the proposition that the crime of failing to update a registry begins in the state from which a sex offender moves.”).
The venue cases referenced in Murphy relied on the federal venue statute, 18 U.S.C. § 3237, which also permits a fail*1093ure-to-register violation to be prosecuted in the district from which the sex offender departs. For offenses that take place in several federal districts, like § 2250, the federal venue statute provides guidelines on the appropriate venue for criminal indictment. 18 U.S.C. § 3237(a). The statute states that “[e]xcept as otherwise expressly provided by enactment of Congress, any offense against the United States begun in one district and completed in another, or committed in more than one district, may be inquired of and prosecuted in any district in which such offense was begun, continued, or completed.” Id.
This court has found that § 2250 describes a continuing offense. United States v. Hinckley, 550 F.3d 926, 936 (10th Cir.2008) (“An interpretation of the sex offender registration requirement that defines it in any way other than as a continuing offense would result in absurdity.”), abrogated on other grounds by Reynolds v. United States, — U.S. —, 132 S.Ct. 975, 181 L.Ed.2d 935 (2012). Although Hinckley did not involve a question of venue per se, the panel’s finding that § 2250 is a continuing offense places that statute squarely within the ambit of § 3237. Moreover, construing § 2250 as a continuing offense that is subject to the federal venue statute is reasonable and comports with the general purpose behind SORNA. Indeed, the subdivision of § 2250 applicable here, which covers offenders convicted under state law, intended “to subject to federal prosecution sex offenders who elude SORNA’s registration requirements by traveling in interstate commerce.” Carr, 560 U.S. at 456, 130 S.Ct. 2229.
From this, we derive two simple principles that describe the relevance of § 2250’s status as a continuing offense for venue purposes. The first is that a potential offense under § 2250 extends from the moment a sex offender abandons his residence in the departure jurisdiction, see Murphy, 664 F.3d at 802-03, until the peripatetic fugitive either registers or is arrested. See United States v. Pietrantonio, 637 F.3d 865, 870 (8th Cir.2011) (“[A]U of the courts that have recognized a ‘continuing’ SORNA violation have found that the violation continues until the defendant is arrested or registers.” (emphasis in the original)).
And the second is that this act of interstate travel creates two (or possibly more) venues in which the crime could be prosecuted. The plain language of § 3237’s invitation to prosecute the crime in “any district” where the offense was “begun, continued, or completed” can only be read to create more than one option for the government to lay venue. 18 U.S.C. § 3237; see also United States v. Clark, 728 F.3d 622, 624 (7th Cir.2013) (“[Section] 3237(a) is predicated on the assumption that, for certain offenses, the district in which an offense is ‘begun’ will not be the district in which is it [sic] ‘continued’ or ‘completed.’ ”). When applied to § 2250, the departure location is plainly the district where the offense started.
It is unsurprising, then, that every circuit to address the application of § 3237 to the criminal component of SORNA has found that venue is proper in the departure district of the offender who travels in interstate commerce. See United States v. Leach, 639 F.3d 769, 771-72 (7th Cir.2011); United States v. Van Buren, 599 F.3d 170, 175 (2d Cir.2010); Howell, 552 F.3d at 717-18; see also United States v. Stewart, 461 Fed.Appx. 349, 351-52 (4th Cir.2012); United States v. Atkins, 498 Fed.Appx. 276, 277 (4th Cir.2012); United States v. Burns, 418 Fed.Appx. 209, 213 (4th Cir. 2011). Like the district court here, the only other lower courts in this circuit to *1094consider the question have followed the lead of this almost-unanimous authority. United States v. Cochran, No. CR-08-18-RAW, 2008 WL 2185427, at *2-3 (E.D.Okla. May 23, 2008); United States v. Tong, CR-08-20-RAW, 2008 WL 2186205, at *2-3 (E.D.Okla. May 23, 2008).5
Lewis’s interstate travels began in Kansas and ended in Georgia. Because his offense was ongoing, his stopover in Missouri does not divest either Kansas or Georgia of their status as a proper venue. Had he registered in Missouri, then the inquiry may be different because Kansas would have lost its nexus to his offense. But in the moments before his arrest in Georgia in July 2012, Lewis was committing an ongoing violation for a failure to update his registration when he abandoned his residence in Kansas and then moved across state lines. Upon his arrest, he was subject to prosecution in Kansas for his continuing offense. Section 3237 yields this clear conclusion.
Regardless of the analytical path we take — Murphy, § 3237, or some combination of the two — our reasoning converges at the same result: venue for a failure to register under § 2250(a) is proper in the departure district.
3. Lewis’s Other Arguments
Lewis makes three additional arguments, all based on a theory that the evidence does not place Lewis in Kansas between August 5, 2011 and July 25, 2012— the dates listed on the indictment. To start, he appears to claim that his abandonment of his Kansas residence likely occurred long before the period charged in the indictment. Thus, according to Lewis, he was not violating SORNA during the time period articulated by the government, and the triggering obligation, to the extent one existed, took place outside of the indictment window. On these grounds, Lewis suggests Murphy is distinguishable because the defendant in that case clearly was in Utah within the temporal time frame charged by the indictment.
This argument, however, is flawed. Regardless of when Lewis left, he was violating the statute in Kansas during the indictment period because he never registered anywhere else. Kansas remained a jurisdiction involved, and there was sufficient evidence to show that (1) he abandoned his Kansas residence at some point in time; and (2) he never registered anywhere else during the indictment period. For this reason, he remained in violation of SORNA in Kansas until he updated his registration or, as here, was arrested.
Second, Lewis contends that the limited factual record permits an inference that he was still compliant with his registration requirements prior to October 1, 2011 because his periodic registration deadline6 *1095had not yet passed and he had not yet changed his residence under SORNA. Boiled down, this is just an argument that he never abandoned Kansas and thus was not required to update his registration until the next recurring registration date arrived. Accepting this argument would, in effect, grant sex offenders a license to be transitory, to move from place to place evading the registration requirements but maintaining their residence in a single district. Cf. Voice, 622 F.3d at 875 (“We reject the suggestion that a savvy sex offender can move to a different city and avoid having to update his SORNA registration by sleeping in a different shelter or other location every night”). This line of reasoning is also mooted when the government proves by a preponderance of the evidence that the sex offender abandoned his departure residence. In this case, the government proved through evidence at trial that Lewis had abandoned his Kansas residence, and we see no error in that determination.7
Finally, in his most all-encompassing argument, Lewis alleges that the government’s theory of the case is premised on the idea that a sex offender has an affirmative duty under federal law to tell the departure state he is leaving and moving to another state. But as we have said, this is only a partial truth: the offender is only required to inform the departure jurisdiction that he is leaving or has left if he does not register elsewhere within three days of departure. There is no unconditional obligation under federal law to contact the departure district; you are merely subject to prosecution in that jurisdiction if you fail to meet your obligation somewhere else.
On this point, Lewis relies on United States v. DeJarnette, where the Ninth Circuit found that “the jurisdiction from which an offender departs is [not] always a jurisdiction involved pursuant to subsection (a) [of § 16913].” 741 F.3d 971, 984 (9th Cir.2013). In DeJarnette, the defendant was convicted of sex crimes in California in 2001. He became a serial flouter of state and federal registration requirements and then absconded from California to Georgia in March of 2008. SORNA became retroactively applicable to pre-Act offenders in August of 2008, at which point the government indicted the defendant for violating SORNA’s initial registration requirement in California. Unlike post-Act offenders, the Ninth Circuit found that pre-Act offenders were not required to register in the jurisdiction of their conviction if it was different from their jurisdiction of residence upon SORNA’s retroactive application. Yes, the court did go on to reject the government’s argument that the defendant was required to register in California because it remained a “jurisdiction involved” under subsection (c). But the court did so in the context of establishing the extent of SORNA’s retroactivity and did not consider the circumstances of an offender’s post-Act absconding from his former residence to evade his registration requirement.
In the end, none of these arguments convinces us to abandon our decision that venue for a § 2250 violation can lie in the departure district.
*1096III. Conclusion
Finding that Lewis was subject to prosecution in Kansas, we AFFIRM the district court’s decision denying Lewis’s motion for a judgment of acquittal based on insufficient evidence of proper venue.