A Lei Complementar nº 87, de 13/09/96, que dispõe sobre o imposto sobre operações relativas à circulação de mercadorias e sobre prestações de serviços de transporte interestadual e intermunicipal e de comunicação - ICMS, nos seus artigos 11 e 12, estabelece:
"Art. 11 O local da operação, para os efeitos da cobrança do imposto e definição do estabelecimento responsável, é:
(...)
II - tratando-se de prestação de serviço de transporte:
a) onde tenha início a prestação;
(...)
Art. 12 Considera-se ocorrido o fato gerador do imposto no momento:
(...)
V - do início da prestação de serviços de transporte interestadual e intermunicipal, de qualquer natureza;
(...)". (Destacou-se).
Cada estado tem sua Legislação completar, que consolida as normas referente ao ICMS. Portanto de acordo com a legislação acima transcrita, o imposto é devido para o Estado onde começa a prestação de serviço.
No caso exposto, a prestação de serviço iniciada em RS para entrega da mercadoria no território Paulista, encerrou quando da finalização do trajeto contratado.
Ao fazer um novo frete para outro estado, inicia-se nova prestação de serviço neste caso, o ICMS relativo à esta prestação de serviço de transporte, deve ser calculado com base na legislação paulista, por ser este o local onde está se iniciando a prestação de serviço.