We generalize Markowitz analysis to the situations involving an uncertain exit time. Our approach preserves the form of the original problem in that an investor minimizes portfolio variance for a given level of the expected return. However, inputs are now given by the generalized expressions for mean and variance-covariance matrix involving moments of the random exit time in addition to the conditional moments of asset returns. While efficient frontiers in the generalized and the standard Markowitz case may coincide under certain conditions, we demonstrate, by means of an example, that in general that is not true. In particular, portfolios efficient in the standard Markowitz sense can be inefficient in the generalized sense and vice versa. As a result, an investor facing an uncertain time-horizon and investing as if her time of exit is certain would in general make sub-optimal portfolio allocation decisions. Numerical simulations show that a significant efficiency loss can be induced by an improper use of standard mean-variance analysis when time-horizon is uncertain.