The work by the Austrian expressionist Egon Schiele went under the hammer at Sotheby's as part of the Impressionist and Modern Art evening sale.
It was bought for £12,661,600, including buyer's premium, by an anonymous bidder - a record for the artist at an auction and the most expensive restituted impressionist work ever sold at an auction.
Painted in 1916, Krumauer Landschaft (Stadt und Fluss) or Landscape at Krumau, is a vibrant depiction of the small town of Krumau on the banks of the Moldau river in Bohemia, which was Schiele's mother's birthplace.
The painting was seized by the Nazis from the home of Wilhelm and Daisy Hellmann in Vienna in 1938. They had bought it directly from Schiele, who was a personal friend.
The work was put up for sale in Vienna in 1942 and bought by Wolfgang Gurlitt who sold it to the Neue Galerie in Linz in January, 1953, where it had been on public display until its restitution earlier this year to Mr and Mrs Hellmann, the heirs of the original collectors. Erika Jakubovits, executive director of the presidency of the Jewish community in Vienna, said: "Sixty years on, it is important to recognise the enduring rights of victims and their heirs.
"We would like to thank the mayor of the city of Linz and all others who have been involved for their recognition of the moral obligation to return this painting."