Alexandru Șoltoianu wurde 1934 in dem Dorf Inești im damals noch rumänischen Bessarabien in eine bäuerlichen Familie geboren. 1959 nahm er – Bessarabien war inzwischen Teil der Moldauischen Sozialistischen Sowjetrepublik – am Moskauer Staatlichen Institut für Internationale Beziehungen ein Studium auf, das er 1965 abschloss. Anschließend kehrte er nach Moldau zurück und lehrte zwei Jahre lang afrikanische und asiatische Geschichte an der Universität Chișinău. Nebenher verfasste er außenpolitische Kommentare für den moldauischen Rundfunk und das Fernsehen. 1967 zog er zurück nach Moskau, wo er als Redakteur im sowjetischen Rundfunk arbeitete und 1969 in die Programmabteilung für die Länder des Nahen und Mittleren Ostens übernommen wurde. Anschließend arbeitete er als Ökonom im Wissenschaftlichen Forschungsinstitut des Staatlichen Komitees für Arbeit und Löhne beim Ministerrat.
Șoltoianu gründete Anfang der 60er Jahre in Moskau eine illegale Gruppe als Vertretung der moldauischen Landsmannschaft und entschied sich später dazu, eine Organisation mit dem Namen „Nationale Wiedergeburt Moldaus“ zu schaffen. Diese Idee diskutierte er mit seinen engsten Gefährten, entwickelte eine Organisationsstruktur für diese künftige Bewegung und formulierte ihr Programm, das unter anderem die Einführung des lateinischen Alphabets vorsah. Wichtige weitere Ziele waren eine Wende in der Bevölkerungspolitik, um die Abwanderung der indigenen Moldauer zu beenden, die Vereinigung Moldaus mit Rumänien und die Rückgabe jener Gebiete an Rumänien, die mit dem Hitler-Stalin-Pakt an die Sowjetunion gefallen waren.
1971 durchsuchte der KGB Șoltoianus Wohnung und beschlagnahmte seine handschriftlichen Manuskripte. Șoltoianu hatte zuvor viele Jahre an einem Buch gearbeitet, in dem er die Innen- und Außenpolitik der Sowjetunion kritisierte. Er wurde als Zeuge im Prozess gegen Gheorghe Ghimpu, Valeriu Graura und Alexandru Usatiuc nach Chișinău verbracht, am 13. Januar 1972 selbst verhaftet und nach Artikel 67, Paragraf 1 und Artikel 69 Strafgesetzbuch der Moldauischen Sowjetrepublik angeklagt (siehe Artikel 70 Strafgesetzbuch der RSFSR und Artikel 72 Strafgesetzbuch der RSFSR). Am 4. Januar 1972 verurteilte ihn das Oberste Moldauische Gericht zu einer Gefängnisstrafe von sechs Jahren sowie zu fünf Jahren Verbannung. Seine Strafe verbüßte Șoltoianu in den mordwinischen Lagern und in den Permer Lagern. Anschließend wurde er nach Kasachstan in das Gebiet Qysylorda verbannt.
Nach seiner Rückkehr aus Lagerhaft und Verbannung im Januar 1983 lebte Șoltoianu in der zweitgrößten moldauischen Stadt Tiraspol. 1988 zog er nach Moskau um. Als er dort 1990 als Volksdeputierter der Russischen Sozialistischen Föderativen Sowjetrepublik kandidieren wollte, lehnte die zentrale Wahlkommission seine Registrierung jedoch ab. Daraufhin kehrte er nach Moldau zurück und wurde noch im selben Jahr Berater im Ministerium für Nationale Sicherheit. Nachdem 1994 linke Kräfte an die Regierung gekommen waren – die Republik Moldau war seit 1991 ein unabhängiger Staat –, entfernte man ihn aus seinem Amt. 1998–2000 war Șoltoianu stellvertretender Vorsitzender des Exekutionskomitees des Verbands der Opfer der kommunistischen Okkupation und der Kriegsveteranen der rumänischen Armee. Viele Jahre lebte er als Rentner in Moskau.
Alexandru Șoltoianu starb am 13. April 2022.