At a ceremony in Warsaw, Prince Andrew thanked the Polish Prime Minister, Jerzy Buzek, for Poland's pivotal role in cracking Nazi Germany's Enigma code.
Poland has long said its mathematicians broke the Enigma code used by the Nazis to send secret orders and messages.
Poles have accused the UK of failing to acknowledge their country's codebreaking achievement.
Some historians suggest the cracking of Enigma may have shortened World War II by several years.
The Nazis used Enigma to direct ships, submarines and armies on all war fronts.
The Japanese also used a modified version of Enigma, which was duplicated by the Americans.
Polish role
Prince Andrew handed over an Enigma machine taken from a captured Nazi submarine, as a "symbol of our gratitude".
"The Enigma codes would not have been broken if it were not for the knowledge of Polish mathematicians," he was quoted as saying at the start of a two-day visit.
Mr Buzek said he was "greatly satisfied" that the UK officially recognised that Enigma was decoded by the Poles.
Polish historians say three Polish mathematicians - Marian Rejewski, Jerzy Rozycki and Henryk Zygalski - broke the Enigma code in 1933.
In July 1939, just before the war, Poland gave Britain and France replicas of the Enigma encoding machine, helping the Allies decipher secret Nazi messages.
According to British accounts, British cryptographers cracked the code a year before war broke out.
Mr Buzek asked Britain on Monday to change the Encyclopaedia Britannica entry on Enigma to credit the Poles for their role in breaking the system.
A British-Polish Joint Historical Commission has been set up to clear up fallacies and misconceptions about the two countries' war-time roles.
After the Nazis invaded Poland in September 1939, the three Polish mathematicians escaped to France.
They went on to work for the intelligence services based at the Bletchley Park decoding centre.
British cryptographers went on to break successively more sophisticated German codes throughout the war.
UK police are still trying to track down another Enigma code machine stolen on 1 April from Bletchley Park Museum.