Como questor, em 104 a.C., Saturnino supervisionou a importação de cereais no porto mediterrâneo de Óstia, mas acabou sendo removido pelo Senado, um procedimento raro, e substituído por Marco Emílio Escauro, um membro da facção dos optimates, representantes da aristocracia romana. Aparentemente Apuleio não chegou a ser processado por incompetência ou má gestão e a atualmente acredita-se que esta troca arbitrária tenha lançado Saturnino nos braços dos mais extremados populares.
Em 103 a.C., Saturnino foi eleito tribuno da plebe. Num acordo com Caio Mário, ele conseguiu o apoio de seus soldados propondo que cada um de seus veteranos deveria receber um lote de 100 jugera de terras na província romana da África. Mais tarde, Saturnino teria um papel fundamental em assegurar a eleição do próprio Mário ao seu quarto consulado, no ano seguinte.
Uma oportunidade para retaliar contra os nobiles da facção adversária se apresentou com a chegada, em 101 a.C., de embaixadores de Mitrídates VI do Ponto portando grandes quantias de dinheiro para subornar os senadores romanos; revelações comprometedoras foram feitas por Saturnino, o que insultou os embaixadores. Ele foi processado por violar a "lei das nações" e só escapou da condenação por um apelo à misericórdia ("ad misericordiam") do povo. É ao primeiro tribunado de Saturnino que geralmente se atribui sua Lex Appuleia de maiestate, cujos termos exatos são desconhecidos, mas que provavelmente tratava de reforçar o poder dos tribunos dos populares ao estabelecer a "minuta maiestas" para os romanos cujos atos fossem considerados prejudiciais à integridade da república, um conceito semelhante ao que se entende como "alta traição" atualmente.
Saturnino detestava particularmente Quinto Cecílio Metelo Numídico, que, durante seu mandato como censor, tentou expulsar Saturnino do Senado acusando-o de imoralidade e só não conseguiu por que seu colega, Caio Cecílio Metelo Caprário, não concordou. Para cair nas graças da população, que ainda celebrava a memória dos irmãos Graco, Saturnino apresentou a Roma, como candidato a tribuno da plebe, um homem que se dizia filho de Tibério Graco, Lúcio Equício. Apesar de Cornélia Africana e Semprônia, mãe e irmã dos Gracos respectivamente, terem rejeitado a reivindicação de Lúcio, a plebe agrediu Metelo Numídico até deixá-lo inconsciente quando ele rejeitou a candidatura.
Segundo tribunado (100 a.C.)
Quando Mário voltou para Roma depois de sua vitória contras os cimbros, ele se viu isolado no Senado e entrou num acordo com Saturnino e seu aliado, Caio Servílio Gláucia e os três formaram uma espécie de triunvirato com o apoio dos veteranos de Mário e da maior parte da plebe. Saturnino e Gláucia prometeram novamente a concessão de terras aos soldados de Mário e, com ajuda de subornos e assassinatos, Mário foi eleito cônsul pela sexta vez em 100 a.C. (quinta consecutiva), Gláucia foi eleito pretor e Saturnino, tribuno da plebe pela segunda vez. Saturnino então apresentou uma lei agrária para ampliar o escopo da que já havia sido aprovada na África e que propunha que todo o território ao norte do rio Pó, recentemente conquistado por Mário dos cimbros, deveria ser utilizado para assentar os veteranos , incluindo terras antes ocupadas pelas tribos celtas. Esta lei provocou uma enorme polêmica, já que estas terras eram, até serem conquistadas pelos cimbros, propriedade de camponeses italianos.
Colônias foram fundadas na Sicília, Acaia e Macedônia com os recursos do infame "Ouro de Tolosa", saqueado indevidamente por Quinto Servílio Cepião, pai de Quinto Servílio Cepião, o Jovem. Diversos povos itálicos foram admitidos nestas colônias, o que era um reconhecimento da igualdade de direito entre eles e os romanos, o que ofendeu profundamente os aristocratas romanos, que defendiam que a cidadania deveria ser restrita aos romanos e não estavam dispostos a ceder mais privilégios.
Uma cláusula exigia a que, passados cinco dias da aprovação da lei, todos deveria defendê-la sob pena de expulsão do Senado e o exílio. Todos os senadores o fizeram, com exceção de Quinto Cecílio Metelo Numídico, que foi exilado. Além disto, Saturnino apresentou um projeto de lei com o objetivo de conseguir o apoio da plebe: o suprimento de cereais a preço de custo. O questor, Cepião, o Jovem, declarou que o tesouro romano não suportaria este subsídio, mas os colegas de Saturnino interpuseram seu poder de veto. Saturnino ordenou que a votação fosse retomada, mas Cepião dispersou o grupo violentamente. O Senado então declarou nula a reunião e invalidou alegando que um trovão indicava o descontentamento dos deuses. Saturnino declarou então que era melhor o Senado permanecer calado, pois ao trovão poderia se seguir granizo. Os projetos de lei de Saturnino, conhecidos como "Leges Appuleiae", acabaram sendo aprovados por conta da influência do cônsul Caio Mário e seus veteranos.
Terceiro tribunato, desgraça e morte
Mário, vendo-se cada vez mais obscurecido por seus colegas, especialmente por conta de seus excesso, rompeu a aliança. Saturnino e Gláucia perceberam que a única esperança que tinham de se manterem a salvo era permanecerem no cargo. Saturnino foi então eleito para um terceiro mandato como tribuno a iniciar em 99 a.C. e Gláucia, mesmo tendo sido pretor havia menos de dois anos, foi candidato ao consulado, o que era irregular. Marco Antônio Orador foi eleito sem oposição e o outro candidato optimate, Caio Mêmio, que era quem aparentemente seria eleito, foi golpeado até a morte por agentes de Saturnino e Gláucia ainda durante a votação.
A morte de Mêmio provocou uma autêntica revolta no sentimento político da cidade. O Senado declarou, no dia seguinte, que Saturnino e Gláucia eram inimigos públicos, e ordenou que Mário agisse para defender a República. Apesar da antiga aliança, não restava alternativa a Mário a não ser obedecer. Saturnino, depois de um breve confronto no Fórum Romano, refugiou-se com seus seguidores no Capitólio e foi obrigado a se render depois que o suprimento de água para o local foi interrompido. Mário, prometendo garantir suas vidas, os levou até a Cúria Hostília com a intenção de processá-los de acordo com a lei, mas os membros mais extremados dos optimates, subiram no telhado da Cúria, arrancaram diversas telhas e apedrejaram Saturnino e seus seguidores. Gláucia, que havia se escondido em uma casa, foi arrastado para a rua e assassinado.
