Leon Trotsky was killed with a mountaineering ice axe in Mexico. The method of murder chosen was interesting. If he was a political fugitive in far off Mexico, why bother dealing with him? What about Trotsky's communist ideology differed from Stalin's and caused the perceived threat to the Soviet state?
Trotsky, as the leader of the Fourth International, was a direct competitor to Stalin as the Leader of the World Worker Movement. Stalin needed all the communists to be subservient to him, especially during the World War.
Squabbles between Stalinists and Trotskyists inside the Spanish Republicans cost them dearly and demonstrated that Trotsky was still a force to be reckoned with.
Don't forget that Stalin had a vengeful personality and wanted to kill Trotsky out of pure spite too.
Stalin was concerned about Stalin and the fate of the Marxist-Leninist-Stalinist world revolution. The success of a Marxist-Leninist-Trotskyist movement would have endangered both his physical survival and his political legacy.
Clarification: I see Stalin as a paranoid tyrant who did take power by force, and was afraid that others would do the same to him. He reacted forcefully to potential rivals, and even more forcefully to actual rivals, which Trotsky was. Trotsky provided a slightly different interpretation of Marxism-Leninism, which was a threat for Stalin who derived his legitimacy from claiming Lenin's heritage.
I think you need to reverse your question: why not kill him?
When the death sentence was passed on Bukharin, Stalin's long-neutralised and powerless former rival, Bukharin was allowed to write a short note to his sometime friend.
Koba, why do you need me to die?
Stalin did not answer these pathetic words. Unlike Trotsky, it would have been no trouble at all for Stalin to keep Bukharin quietly under house arrest. However, Bukharin had to die.
Although Trotsky had absolutely no prospect of overthrowing Stalin as leader of the USSR, he could have made it much harder to galvanise foreign communists, and get sympathy and support from Western governments.
But mainly, Trotsky had crossed him, so Trotsky had to go.
Stalin had Trotsky assassinated for personal reasons. These can be seen if you read The Revolution Betrayed and Stalin by Trotsky, and Stalin: A biography by Robert Service which sums up Trotsky's demise in 1940. Trotsky attacked Stalin politically and personally through his books and while Lenin was alive. Trotsky was mocking Stalin about his physical appearance, shortcomings, and his political incompetence. This greatly offended Stalin which made him take action against Trotsky.
First of all, Trotsky had contested the succession to Lenin with Stalin. If Lenin had been in better health in his last days, Trotsky might have won because Lenin preferred him. So Trotsky was an existential threat to Stalin in the Soviet Union.
The second thing was that Communism was supposed to be a worldwide movement, not just for the Soviet Union. So Trotsky was challenging Stalin's leadership on a global basis, after having lost a succession battle with him in the Soviet Union. Other than Trotsky's succeeding to Lenin, the last thing Stalin wanted was to have say, a Mexican Communist movement challenging the Soviet Communist movement for global supremacy.
The fact that he was a fugitive in Mexico didn't eradicate the fact that he still was having aspirations to get power in the USSR through subversion, foreign invasion etc.
In 1936 Primakov, the deputy commander of the Leningrad military district, was arrested and charged with a counter-revolutionary conspiracy etc. Now the majority of historians say that he was tortured etc. and actually there is no way for an ordinary man, who is seeking truth, to check now whether this was true. But there is one pretty solid, I think, evidence, that he wasn't tortured, as well as his arrested in 1937 fellows. The fact is, that he didn't plead guilty until in 1937 the Soviet intelligence got compromising materials from Germany about the military coup, which was being planned by Tukhachevsky and others. When Tukhachevsky was arrested and saw the acquired evidence he immediately pled guilty (and there was a reason to do that, since the Soviet criminal code at the time did not require the capital punishment for high treason in every case, and Tukhachevsky could have a hope, that he would have been exiled just like Trotsky) and after that immediately Primakov started to speak. They admitted, that they were planning to perform a coup and that behind it was Trotsky.
Also there are interesting memoirs of the wife of Soviet marshal Blyukher, Glafira (see this DjVu file of issue 1 1990 of the Russian language "Military-historical magazine", page 79). He is also considered an honest man, who served his country and was killed by Stalin "just of pure spite". But there are many interesting things told by this woman. She told, how in 1936 general Gamarnik, another "victim" of Stalin, was inspecting the Far East military district.
When Gamarnik was leaving, Blyukher deliberately didn't come to the railway station see him off. And then told his wife that he would catch up Gamrnik's train secretly and after that he would send a cable from Chita to Khabarovsk to the wife. If the cable was about "Lida (a feminine name) is coming" then the wife should stayed, and if "Lida is not coming" that the wife should took the child and immediately left Khabarovks. Isn't this a strange behavior of a Soviet general?
After the meeting Blyukher told his wife, that Gamarnik had suggested to "arrange" her arrest and charge with espionage, and to make it look as if Blyukher himself was not aware of anything. But Blyukher refused, saying that she was not only his wife, but "the mother of his child". Interesting talking was in the ranks of Soviet generals, isn't it? Blyukher had no problem with an innocent man been executed, the only thing he was against in this brilliant plan, is the mother of his child being such a man. Isn't this a considerable circumstantial evidence of something very strange happening in the Red Army under Tukhachevsky's command?
The point of this cases is that Trotsky was not simply sitting in Mexico and writing memoirs, as did many other ideological enemies of the Bolsheviks in the world, like Kerensky, for instance. He was actively waging a subversive war on the USSR, that is why he had to be assassinated.
I know that many people here will say that Tukhachevsky, Trotsky and others were completely innocent and Stalin was a spiteful villain, who simply wanted everyone killed and the military coup never existed, just because he could never exist. But look around, don't you see that in the world today powers are actively engaged not only in the overt strife, but in a secret one too. Suppose that in 2016 in Turkey president Erdogan had not waited for the military to bomb the parliament and arrested them before the active stage of the coup. Wouldn't have today's "democrats" on CNN be wining about vengeful villain Erdogan arresting and sentencing "innocent victims" just because he is seeking more power for himself because of spite?
And the method to kill Trotsky with the ice ax was not because Stalin wanted Trotsky to suffer more, but because Trotsky had a very strong armed guard. It was considered not possible to approach Trotsky with a firearm or something else. The man, who killed him, Ramon Mercader, was planted into Trotsky's circle and waited for a moment for a long time (more than a year, as I remember from Sudoplatov's memoirs).
A commentator has suggested me to provide all sources. So let me add some additional information to this.
First, my answer is not based only on "Glasha's tale". The fact that Primakov, the deputy commander of the Leningrad military district, was arrested in 1936 and was denying the charges for more than a year is a well-known, easy to check in numerous sources fact. The same story is with Putna, who was arrested on August, 20, 1936. Were they able to endure "terrible Stalin's tortures"? And why wasn't Tukhachevsky able to do the same just for four days (he was arrested on May, 22, then transported to Moscow and on May, 26, after confrontation interrogations with Putna, Primakov and Feldman, started giving first testimonies)?
The second point is that Tukhachevsky's case, is still classified, as well as Blyukher's one, so there is no way for me to provide direct evidence as well as for other "historians", who were even allowed to the archives, since they do not provide documents but only excerpts from them in their own interpretation, often biased or outright distorted. The trials of Tukhachevsky and other Trotsky's conspirators were open, with numerous journalist with defendants presented openly to the public. But their rehabilitation was outright secret, with no evidence or public open discussion.
The third point. In 1938 lieutenant-general of the NKVD Lyushkov defected to Japan. Officially the Japanese propaganda stated that he had become "disillusioned" with Stalin, that all Trotsky conspiracies never existed etc. But there are fragmentary evidences of what he was telling the Japanese in earnest.
Sorge had alredy learned from Schol everything that the Japanese had learned from Lyushkov, and he sent this information to Moscow by radio. Sorge's report included Lyushkov's personal statement of his anti-Communist attitude, his opinion on the extent and strength of anti-Moscow factions withing the Soviet Far East Army…
… the fact that his [Blyukher's] death did not receive the usual purge publicity raises the possibility that Sorge's report had implicated him in one plot that was not fabricated by Stalin.
This is from "An Instance of Treason: Ozaki Hotsumi and the Sorge Spy Ring" by Chalmers A. Johnson.