Background: Opioid-induced constipation (OIC) is common in critically ill patients; it leads to complications that can increase hospital stay and, rarely, bowel perforation. Opioid antagonists are considered a logical approach to treat OIC; however, the agent of choice has yet to be determined. Objective: To assess the effectiveness and safety of enteral naloxone (NTX) versus subcutaneous methylnaltrexone (MNTX) for the treatment of OIC in the medical intensive care unit. Methods: This retrospective review evaluated patients who received fentanyl continuous infusions for at least 72 hours and were initiated on NTX or MNTX. Active colitis, mechanical gastrointestinal obstruction, and inability to receive NTX orally were exclusion criteria. The primary outcome was time to first bowel movement (BM). Secondary outcomes included total number of BMs within 48 hours, opioid requirements after NTX or MNTX, and change in any of the following after the opioid antagonist: heart rates, mean arterial pressures, and level of sedation. A post hoc subgroup analysis of patients on vasopressors was conducted. Results: Baseline characteristics were similar between patients receiving NTX (n = 52) and MNTX (n = 48), except the MNTX group required a higher median norepinephrine dose (0.22 vs 0.1 µg/kg/min, P = 0.001). The median times to first BM for NTX and MNTX were 30 and 24 hours (P = 0.165). There was no difference in the primary outcomes for patients on vasopressors. Both groups did not require additional fentanyl equivalents, as evidenced by stable vitals and opioid requirements during treatment. Conclusions: Both agents appear to be effective and safe for the treatment of OIC; however, future controlled prospective trials are warranted.