Cuba había solicitado la negociación de este acuerdo en 2003, pero el inicio de las tratativas se demoró por resistencias de parte del gobierno uruguayo de la época.