A continuous-time version of the Markowitz mean-variance portfolio selection model is proposed and analyzed for a market consisting of one bank account and multiple stocks. The market parameters, including the bank interest rate and the appreciation and volatility rates of the stocks, depend on the market mode that switches among a finite number of states. The random regime switching is assumed to be independent of the underlying Brownian motion. This essentially renders the underlying market incomplete. A Markov chain modulated diffusion formulation is employed to model the problem. Using techniques of stochastic linear-quadratic control, mean-variance efficient portfolios and efficient frontiers are derived explicitly in closed forms, based on solutions of two systems of linear ordinary differential equations. Related issues such as a minimum-variance portfolio and a mutual fund theorem are also addressed. All the results are markedly different from those for the case when there is no regime switching. An interesting observation is, however, that if the interest rate is deterministic, then the results exhibit (rather unexpected) similarity to their no-regime-switching counterparts, even if the stock appreciation and volatility rates are Markov-modulated.