We formulate a novel Markov regime-switching factor model to describe the cyclical nature of asset returns in modern financial markets. This factor model allows us to estimate the asset expected returns and their covariance matrix. By design, these two parameters implicitly describe the properties of the different market regimes. In turn, these regime-dependent parameters serve as the inputs during portfolio optimization, thereby constructing portfolios adapted to the current market environment. This model can be improved by periodically rebalancing the portfolios, ensuring proper alignment between the estimated parameters and the transient regimes. An out-of-sample computational experiment over a long investment horizon shows that the proposed regime-dependent portfolios are better aligned with the market environment, and can consistently outperform competing portfolios.