This work examines the impact of discharge decisions under uncertainty in a capacity-constrained high-risk setting: the intensive care unit (ICU). New arrivals to an ICU are typically very high-priority patients and, should the ICU be full upon their arrival, discharging a patient currently residing in the ICU may be required to accommodate a newly admitted patient. Patients so discharged risk physiologic deterioration, which might ultimately require readmission; models of these risks are currently unavailable to providers. These readmissions in turn impose an additional load on the capacity-limited ICU resources. We study the impact of several different ICU discharge strategies on patient mortality and total readmission load. We focus on discharge rules that prioritize patients based on some measure of criticality assuming the availability of a model of readmission risk. We use empirical data from over 5,000 actual ICU patient flows to calibrate our model. The empirical study suggests that a predictive model of the readmission risks associated with discharge decisions, in tandem with simple index policies of the type proposed, can provide very meaningful throughput gains in actual ICUs while at the same time maintaining, or even improving upon, mortality rates. We explicitly provide a discharge policy that accomplishes this. In addition to our empirical work, we conduct a rigorous performance analysis for the family of discharge policies we consider. We show that our policy is optimal in certain regimes, and is otherwise guaranteed to incur readmission related costs no larger than a factor of (p̂ + 1)of an optimal discharge strategy, where p̂ is a certain natural measure of system utilization.