This paper quantifies the impact of means-tested programs - in particular, Medicaid and Public Housing - on the interstate mobility of their beneficiaries. Simulations from a structural model with heterogeneous workers and locations show that beneficiaries' mobility falls by 17.2 percent, with the greatest reduction occurring among the poorest beneficiaries. Around half of this effect stems from the lack of federal coordination in the programs' administrations, i.e., the possibility that a moving beneficiary loses transfers despite being eligible for them. Reducing this probability to zero raises overall welfare, with 5 percent of low-income households obtaining a welfare gain of 1.1 percent.