Arto Tolsa begon zijn voetbalcarrière bij de Finse eersteklasser Kotkan Työväen Palloilijat. Met deze club won hij de Beker van Finland in 1967. In 1968 verhuisde hij naar de Belgische club Beerschot VAC. Hij zou er 192 wedstrijden spelen en 14 keer scoren. Hij won ook tweemaal de Beker van België met Beerschot (1971 en 1979 – tijdens de bekerfinale van 1971, die met 2–1 gewonnen werd van Sint-Truiden, maakte hij het beslissende doelpunt). Hij keerde in 1979 terug naar het Finse Kotkan Työväen Palloilijat, waar hij – na een laatste bekeroverwinning in 1980 – zijn actieve loopbaan zou beëindigen in 1982. Tijdens zijn hele voetbalcarrière scoorde hij 126 keer. In 1964 was hij topscorer in de Veikkausliiga (de Finse eredivisie) met 22 goals.
Het stadion van FC KooTeePee (het vroegere Kotkan Työväen Palloilijat voor wie Tolsa had gespeeld) werd uit eerbetoon aan Tolsa omgedoopt tot de Arto Tolsa Areena.