Paul Topainer wurde 1898 in Wien in einer kinderreichen Arbeiterfamilie geboren. Er leistete im Ersten Weltkrieg Militärdienst und war Kriegsgefangener in Italien von 1918 bis 1920. Nach der Entlassung aus der Gefangenschaft trat er 1920 in die SDAP ein, der er bis 1933 angehörte. 1934 trat er in die KPÖ ein. Im Schutzbund war er Kommandant eines Zuges. Von 1926 bis Februar 1934 arbeitete Topainer im Gaswerk Leopoldau. Nach der Teilnahme an den Kämpfen in Wien-Floridsdorf im Februar 1934 wurde er zur Verhaftung ausgeschrieben und flüchtete über die ČSR im April 1934 mit dem ersten Schutzbundtransport nach Russland, wo er als Maler in mehreren Moskauer Betrieben arbeitete, u.a. zusammen mit  Franz Leschanz in der Werkstatt des für die Moskauer Stadtbildgestaltung verantwortlichen Betriebes Мосгороформление. Topainer wurde am 28. März 1938 verhaftet und am 19. September 1938 wegen Spionage zu fünf Jahren Lagerhaft verurteilt. Sein Fall stand im Zusammenhang mit der - nur in der Phantasie der NKVD-Mitarbeiter - aus neun Personen bestehenden „Spionageorganisation“, die angeblich von dem Schutzbündler  Johann Pischa geleitet wurde. Das Urteil wurde am 25. April 1940 revidiert und Topainer als unerwünschter Ausländer des Landes verwiesen. Er wurde Ende April 1940 bei Brest-Litovsk an die deutschen Behörden ausgeliefert. Topainer war eigentlich staatenlos, denn die österreichische Staatsbürgerschaft war ihm am 19. November 1937 aberkannt worden.