Weinheimer, gelernter Autoschlosser, sah 1950 erstmals mit Goethes „Faust“ eine Theateraufführung. Davon war er so beeindruckt, dass er sich entschied, selbst Schauspieler zu werden. Er bewarb sich bei der Staatlichen Schauspielschule Berlin und beendete diese mit Erfolg. Als Horst Schönemann 1954 als Oberspielleiter an das Stadttheater in Senftenberg berufen wurde, nahm er mehrere Absolventen der Schauspielschule, darunter auch Horst Weinheimer, mit. Gemeinsam mit Horst Schönemann ging dieser 1959 nach Berlin an das Maxim-Gorki-Theater, wo er bis 1965 blieb. Von hier aus ging es anschließend an die Volksbühne Berlin und dann 1968 an das Deutsche Theater.