Pada masa SMA, Connie dijodohkan dengan seorang pria bernama Karsana, yang merupakan saudara jauh keluarganya. Meskipun awalnya Connie merasa ingin menikah, namun ia merasa bahwa jodohnya tidak akan bertahan lama. Keyakinan itu terbukti saat pernikahannya dengan Karsana hanya berlangsung singkat, meskipun mereka memiliki seorang putra bernama Agus Sutedja. Setelah bercerai, Connie tidak menyalahkan siapa pun, dan saat itu dia sudah terlibat dalam ajang Ratu Vespa. Setelah pernikahan pertamanya, Connie kembali jatuhmenjalin cinta padadengan Moeslim Taher, seorang Rektor Universitas Jayabaya periode 1962-1988, yang telah lama menyimpan perasaan pada Connie. Meskipun awalnya tidak ingin menikah lagi, Connie akhirnya menyetujuinya pada tahun 1983. Namun, pernikahan kedua Connie hanya bertahan singkat dengan tidak memiliki keturunan. Dua tahun setelahnya, Connie bercerai lagi karena ketidaksetujuan untuk kembali aktif dalam dunia film, yang merupakan puncak karirnya saat itu. Pasca perceraian keduanya, Connie merasa dapat kembali fokus pada karirnya.<ref>{{Cite web|date=2019-04-22|title=Peran Connie Sutedja di Dunia Nyata|url=https://historia.id/kultur/articles/peran-connie-sutedja-di-dunia-nyata-v2e41|website=Historia - Majalah Sejarah Populer Pertama di Indonesia|language=id-ID|access-date=2024-03-09}}</ref>
