ICMS sobre frete

Prezado (a) (s),

Uma empresa que presta serviços de transportes, localizada na Bahia, é contratada por outra empresa, também sediada na Bahia, para realizar o serviço de transporte. A mercadoria que será transportada encontra-se em outro Estado (MG). Em que momento ocorre o fato gerador do ICMS-frete, na saída do veículo da sede da empresa (Bahia), ou no momento em que este veículo sai da empresa (MG) onde encontra-se a mercadoria? O ICMS sobre o frete será pago ao Estado da Bahia ou ao de Minas Gerais?
Quem deve pagar este ICMS, o destinatário ou a transportadora, visto que não há um contrato de continuidade do serviço?

Atenciosamente,

O fato gerador ocorre no início da prestação do serviço em Minas Gerais. O ICMS pertence a Minas Gerais, pertence ao Estado de início da prestação de serviço.
Quem deve pagar é a transportadora!
Obs. A legislação permite atribuir a responsabilidade ao remetente, destinatário e no caso de subcontratação ao transportador de fato (esses casos são exceções).