Ms. Kelly стал первой сольной записью певицы за четыре года. Перед официальным релизом альбом несколько раз переименовывался, сдвигались сроки выпуска. Изначально планировалось издать альбом в середине 2006 года; сдвиг сроков объяснялся многошаговой маркетинговой стратегией, а также дополнительными сессионными записями.