Edelstein ist die Tochter des jüdischen Ehepaars Alvin und Bonnie Edelstein. Sie wuchs in Boston, Massachusetts auf und studierte Theater an der New York University. Während des Studiums begann auch ihre Karriere als Schauspielerin. Ihre erste Filmrolle hatte sie in Oliver StonesThe Doors (1991). Nach vielen Produktionen unter anderem am Broadway schrieb und spielte sie im Musical Positive Me am Ellen Stuart’s La Mama, in Manhattan. Positive Me war eines der ersten Musicals, das sich mit AIDS auseinandersetzte.
Erste Erfahrung im Fernsehen sammelte Edelstein als Moderatorin der Show Awake on the Wild Side. Danach spielte sie in verschiedenen Fernsehserien eine große Bandbreite von Rollen. Einige Beispiele dafür sind eine Edel-Prostituierte in The West Wing, eine Transfrau in Ally McBeal, eine sexbesessene Künstlerin in Frasier und eine jüdisch-orthodoxe Frau, die den Rückhalt ihrer Familie verliert, in Family Law. Auch in der Sitcom Seinfeld hatte sie einige Auftritte. Weiterhin spielte sie in Practice – Die Anwälte die Freundin von James Spader. Von 2004 bis 2011 spielte sie die Dr. Lisa Cuddy in der Erfolgsserie Dr. House, die sie nach der siebten Staffel verließ.