Background: Eastern Europe and Central Asia have intertwined HIV and incarceration epidemics, concentrated in people who inject drugs. Moldova is one of the few countries in this region that offers methadone within prisons, but uptake and post-release retention remains suboptimal. Screening, brief intervention, and referral to treatment (SBIRT) procedures are a potential implementation strategy to address this problem. Methods: From June 1, 2017 to March 3, 2018, we conducted a 2-stage SBIRT strategy in nine prisons and four pre-trial detention facilities in Moldova among incarcerated persons with opioid use disorder (OUD; N = 121) and within 90 days of release. Survey results were analyzed to evaluate the effect of the SBIRT strategy on the uptake of and post-release retention on methadone maintenance treatment (MMT). Results: Among the 121 screened with OUD, 27 were on MMT at baseline within the prison and this number increased to 41 after the two-step SBIRT intervention, reflecting a 51.9% increase over baseline. Eleven (78.6%) of the 14 participants that newly started MMT did so only after completing both SBIRT sessions. The brief intervention did not significantly improve knowledge about methadone but did improve attitudes towards it. Among the 41 participants who received methadone during this trial, 40 (97.6%) were retained 6 months after release; the one participant not retained was on methadone at the time of the intervention and had planned to taper off. Conclusion: The SBIRT strategy significantly improved participant attitudes, but treatment initiation mostly occurred after completing both sessions, including soon after release, but remained low overall. Work within the Moldovan prison subculture to dispel negative myths and misinformation is needed to further scale-up OAT in Moldova.