舞台は前作『侍女の物語』から15年後の世界、三人の女性の視点から語られる。
一人目は前作にも登場し、女性の最高権力者に上り詰めたリディア小母である。ギレアデ共和国成立前、リディアはアメリカ合衆国で教師などを経て判事を務めていた。しかし、クーデター軍が知識層の女性たちを逮捕し、リディアも凄惨な拷問を受ける。拷問に耐え抜いた数名の女性たちは、司令官からギレアデに従うか否かを迫られる。リディアは従属の道を選び、ギレアデの上層部に迎合することで生き延びてきた。その一方でひそかにギレアデ転覆を画策し、手記を残す。
二人目は、司令官の娘アグネス・ジェミマである。アグネスは「妻」となるために大切に育てられ、ギレアデの教えに従って生きてきた。しかし、司令官の後妻である継母に疎まれ、はるかに年上の司令官との結婚を強制される。結婚から逃れるため、友人のベッカと共に小母となるための養成施設「アルドゥア・ホール」に入り、小母見習い「誓願者」となる。
三人目はカナダのトロントに住む古着屋の娘デイジーである。16歳の誕生日、両親をギレアデのテロリストに殺される。反ギレアデ組織「メーデー」に保護され、自身の出自の秘密を知る。そして、ギレアデ内部にいる情報提供者から重要な機密文書を受け取る任務を依頼される。戸惑いつつも覚悟を決めたデイジーは、名前をジェイドと偽り、ギレアデに潜入する。無事アルドゥア・ホールに着くも、ジェイド(デイジー)は異様な雰囲気を漂わせるギレアデを不気味に感じる。
アルドゥア・ホールでリディア小母の案内により、アグネスとベッカ、ジェイドが顔を合わせる。ギレアデしか知らないアグネスとベッカには、自由奔放なジェイドの言動には驚きばかりだったが、3人は友情を育んでいく。
そして、ジェイドはリディア小母から機密文書を託される。リディア小母の計画では、アグネスとベッカが布教のためギレアデを出国すると見せかけて、ベッカとジェイドがすり替わり、文書を国外へ持ち出すこととなった。ジェイドはアグネスとともに命からがらカナダに到着する。文書には司令官たちの汚職や性加害などのスキャンダルが克明に記されており、ギレアデ共和国は崩壊していく。
アグネスとデイジーの二人は実の母に会う[2]。