Eduard von Winterstein wurde am 1. August 1871 in Wien, Österreich, als Eduard Clemens Franz Freiherr von Wangenheim geboren. Sohn Vater, Freiherr Hugo von Wangenheim, war ein Offizier und Gutsbesitzer, seine Mutter Luise Dub war Schauspielerin, die unter anderem am Wiener Burgtheater auf der Bühne stand. Durch sie kam er bereits sehr früh mit der Welt des Theaters und der Schauspielerei in Berührung – nicht zuletzt dadurch entwickelte sich sein Wunsch, selbst Schauspieler zu werden.

Nach der Scheidung seiner Eltern blieb Eduard bei der Mutter. Wie er später in seinen Memoiren erzählte, führten die beiden zunächst ein "Nomadenleben". Schließlich zogen sie ins thüringische Gotha zu Eduards Onkel Gustav von Wangenheim, der für den Jungen bald ein zweiter Vater wurde.

Mit 16 Jahren verließ Winterstein das Gymnasium, um sich selbst auf das Examen vorzubereiten, welches er in Weimar ablegte. Anschließend begann er, sein Berufsziel des Schauspielers zu verfolgen. Er erhielt (wie auch seine Schwester Clementine) Schauspielunterricht von der Mutter, und im Jahr 1899 wurden die Geschwister an das Fürstliche Theater in Gera engagiert (wo auch die Mutter tätig war). Dort lernte Winterstein unter anderem Theodor Lobe kennen, den er später einen "unverdient Vergessenen" nannte.  

Es folgten Engagements in kleineren Rollen unter anderem in Hof, auf Stralsund, in Gelsenkirchen und Göttingen. Eine bedeutende Station war Annaberg-Buchholz im Erzgebirge. Dort spielte er zur Eröffnung des Stadttheaters im April 1893 die Titelrolle in Goethes "Egmont". Winterstein wurde an dem Theater 'Erster Held und Liebhaber' und trat in hochkarätigen Stücken wie "Hamlet" auf. In seinen Memoiren schrieb er: "Ich war in Annaberg wie neu geboren, war ein ganz anderer Mensch geworden. In diesem kleinen Städtchen war ich erst wirklich zum Schauspieler geworden. (…) So wurde die Annaberger Zeit eine der schönsten in meinem Beruf." Hier lernte Winterstein auch seine erste Ehefrau kennen, die Schauspielerin Minna Mengers; die beiden heirateten 1894, die Ehe hielt jedoch nicht lange; der gemeinsame Sohn Gustav von Wangenheim (*1895, benannt nach dem väterlichen Onkel) wurde ebenfalls Schauspieler.  

Nach weiteren Stationen erhielt Winterstein 1895 einen Dreijahresvertrag am Berliner Schillertheater, wo er als Major von Tellheim in dem Lessing-Lustspiel "Minna von Barnhelm" zu Ruhm kam. Die Rolle der Minna spielte Hedwig Pauly, die er 1899 in zweiter Ehe heiratete. 1898 ging Winterstein ans Deutsche Theater Berlin. Da er dort jedoch vor allem als Zweitbesetzung fungierte, wechselte er ans Lessingtheater. Nachdem er an Max Reinhardts Kleinem Theater in der überaus erfolgreichen Inszenierung von Gorkis "Nachtasyl" auf der Bühne stand, folgte er Reinhardt 1904 zunächst ans Neue Theater am Schiffbauerdamm, dann zurück ans Deutsche Theater. Dort leitete er zudem von 1905 bis 1920 die Schauspielschule.

Anders als manche Bühnenkolleg*innen stand Winterstein dem neu aufkommenden Medium Film sehr aufgeschlossen gegenüber. Sein Debüt vor der Kamera gab er 1910 als Scheich in der orientalischen Tanz-Pantomime "Sumurun", einem Theaterfilm von Max Reinhardts Bühneninszenierung. Ab 1913 übernahm er zahlreiche Hauptrollen in Melodramen, Abenteuergeschichten und Literaturadaptionen. Er war Henny Portens Partner unter anderem in "Märtyrerin der Liebe" (1915), "Die Claudi vom Geiserhof" (1917) und dem Zweiteiler "Die Faust des Riesen" (1917). Zudem spielte er die Hauptrollen in zwei bedeutenden Filmen Robert Reinerts: einen Forschungsreisenden in "Opium" (1919) und einen am Fortschritt zweifelnden Fabrikbesitzer in dem skandalumwitterten Nachkriegsdrama "Nerven" (1919).

In Ernst Lubitschs "Madame Dubarry" (1919), mit Pola Negri in der Titelrolle, gab er den Graf Dubarry; ebenfalls an Negris Seite spielte er den Marchese de Montebello in "Das Martyrium" (1920). Mit Asta Nielsen drehte er "Der Reigen – Ein Werdegang" (1920) und "Hamlet" (1921), in dem Nielsen den Hamlet und Winterstein den dänischen König Claudius gab.

Bis Ende der 1920er Jahre wirkte Winterstein in einer Vielzahl an Produktionen mit, von denen einige heute zu den großen Stummfilmklassikern zählen. Er war ein Kalif in Fritz Langs "Der müde Tod" (1921), der Graf Rudenburg in Murnaus "Der brennende Acker" (1922) und der Fürst von Anhalt-Dessau in dem Historien-Vierteiler "Fridericus Rex" (1923). Er gab den Vater der "Försterchristel" (1926) und verkörperte gleich zweimal den General Leberecht von Blücher: in "Lützows wilde verwegene Jagd" (1927) und in "Napoleon auf St. Helena" (1929), mit Werner Krauß in der Titelrolle.

Der Übergang zum Tonfilm bereitete Eduard von Winterstein keine Probleme, wenngleich er nun meist in Nebenrollen zu sehen war. Wie schon zuvor spielte er vorwiegend hochrangige Militärs, Adelige, Kommissare, Beamte, Professoren und andere Autoritätspersonen. Seine erste Tonfilm-Rolle hatte er als Schuldirektor in Josef von Sternbergs Klassiker "Der blaue Engel" (1930). Er war ein Freiherr in dem Liebesdrama "Trenck" (1932) und ein Amtsrichter in "Mensch ohne Namen" (1932).

Während der Nazizeit konnte Winterstein seine Bühnen- und Filmkarriere nahtlos fortsetzen, auch hier im angestammten Rollenfach. Er gab einen Amtmann in Detlef Siercks "Das Mädchen vom Moorhof" (1935), einen Gerichtsvorsitzenden in "Der Mann, der Sherlock Holmes war" (1937), Professoren in "Die barmherzige Lüge" (1939) und "Robert Koch, der Bekämpfer des Todes" (1939), und den preußischen General Gustav von Manstein in Wolfgang Liebeneiners "Bismarck" (1940) – um nur ein paar Beispiele zu nennen. Auch als Theaterschauspieler blieb er aktiv. Von 1938 bis 1944 war er unter der Leitung Heinrich Georges am Berliner Schillertheater engagiert.

Allerdings ließ sich Winterstein, der sich ansonsten apolitisch gab, auch für einschlägige NS-Propagandafilmen vereinnahmen: so spielte er einen Kommandanten der burischen Armee in "Ohm Krüger" (1941) und einen Lazarett-Chefarzt in "Stukas" (1941). Gegen Kriegsende wurde er vom 'Reichsministerium für Volksaufklärung und Propaganda' auf die 'Gottbegnadeten-Liste' gesetzt. Zu seinen letzten Rollen unter dem Nazi-Regime gehören der Vater des Lügenbarons (Hans Albers) in "Münchhausen" (1943), ein Gerichtsvorsitzender in dem Justizdrama "Der Verteidiger hat das Wort" (1944) und ein Arzt in Paul Verhoevens "Philharmoniker" (1944).  

Nach Ende des Zweiten Weltkrieges schrieb Winterstein seine Memoiren, die er 1947 unter dem Titel "Mein Leben und meine Zeit" veröffentlichte. Er zog in die DDR und spielte noch einige Jahre in West und Ost Theater, so etwa an seiner früheren Wirkungsstätte, dem Deutschen Theater, sowie an der Volksbühne. Zu seinen erfolgreichsten und berühmtesten Bühnenrollen dieser Zeit gehören die Titelfiguren in Lessings "Nathan der Weise" und Goethes "Faust".  

In Filmen der DEFA verkörperte Winterstein oft humanistische, lebenserfahrene und weise Figuren. So auch in seiner ersten, kleineren Nachkriegs-Filmrolle als Vater der Hauptfigur in dem Ostberliner Studentendrama "...und wieder 48!" (1948), bei dem sein Sohn Gustav Regie führte. Für seine Hauptrolle als humanistisch gesinnter Professor in dem Antifaschismus-Drama "Die Sonnenbrucks" (DDR 1951) wurde er auf dem Filmfestival in Karlovy Vary als Bester Darsteller ausgezeichnet. Weitere wichtige Rollen waren der weise Dorfpfarrer in "Das verurteilte Dorf" (DDR 1952) und ein grummelig-gutmütiger Professor in Konrad Wolfs "Genesung" (DDR 1956).  

Sein Sohn Gustav besetzte ihn im Abenteuerfilm "Gefährliche Fracht" (1954) und der Komödie "Heimliche Ehen" (1956), in der der spätere Star Armin Mueller-Stahl sein Kinodebüt gab. Seine letzte Filmrolle hatte Winterstein als Kernphysiker in Kurt Maetzigs Science-Fiction-Film "Der schweigende Stern" (PL/DDR 1960) nach Stanislaw Lem. Danach zog sich der inzwischen 88-jährige, oft "Nestor der Schauspielkunst" genannte Charakterdarsteller ins Privatleben zurück. Seine Filmografie umfasst rund 240 Titel.

Am 22. Juli 1961, nur einige Tage vor seinem 90. Geburtstag, starb Eduard von Winterstein in Berlin. Sein Nachlass wird von der Berliner Akademie der Künste verwaltet. Zu seinen Ehren wurde 1981 das Annaberger Stadttheater in Eduard-von-Winterstein-Theater umbenannt.