Recent archaeological work has supported what locals had long suspected: the palace stands directly on the foundations of an ancient temple to Helios, the sun god, which is also the most plausible site for the Colossus of Rhodes. The 33-meter bronze statue, one of the Seven Wonders of the Ancient World, stood for only 54 years before an earthquake felled it in 226 BC. It lay in massive pieces along the harbor for nearly a thousand years until Arab traders sold the bronze for scrap in the seventh century. The traditional image of the Colossus straddling the harbor mouth is almost certainly wrong. Modern scholars place it on the high ground inside the city, at the spot where the Knights eventually built their headquarters. The foundations underneath the palace are deep, and they are old.

The Knights Hospitaller had been driven from the Holy Land in 1291 with the fall of Acre, and they spent eighteen years on Cyprus before deciding they needed an island of their own. Rhodes belonged nominally to the Byzantine Empire but was poorly defended. The Knights took it in 1309 along with Kalymnos, Kastellorizo, and several smaller islands, converting the existing Byzantine citadel into the palace, headquarters, and fortress they would occupy for the next 213 years. The first quarter of the fourteenth century saw the major modifications. The earthquake of 1481 damaged the palace severely, but the Knights repaired it and held the island through one Ottoman siege in 1480. They did not survive the second. In 1522, after a six-month siege by Suleiman the Magnificent in person, the Knights surrendered Rhodes on terms that allowed them to evacuate to Malta with their archives and their honor.

Under Ottoman rule from 1522 onward, the palace served as a command center and a powder magazine, an unusual combination that would prove costly. The medieval city around it remained largely unchanged, the Street of the Knights still lined with the inns each national tongue of the Order had built for itself. The 1856 explosion under the Church of Saint John, which had stored gunpowder since 1522 and possibly longer, destroyed both the church and most of the palace. The Knights had once built a complex; the Ottomans had used it as a depot; and now what remained was rubble. For the next eighty years, until the Italian period, the palace site sat largely abandoned, a hollow in the medieval town.

Italy seized the Dodecanese from the Ottomans in 1912 during the Italo-Turkish War and held them through World War I and into the Fascist period. From 1937 to 1940, the architect Vittorio Mesturino oversaw the reconstruction of the palace as a holiday residence, first for King Victor Emmanuel III and then for Benito Mussolini himself. Mesturino had medieval drawings to work from, including the 1844 lithograph of the surviving facade, but his sense of what a crusader palace should look like was mostly invented. He added towers, machicolations, and grand staircases that had no archaeological basis. One scholar has called the result horrendous fascist taste. Mussolini's name still appears on a large plaque near the entrance, an awkward souvenir the modern Greek state has chosen to leave in place rather than erase. The palace was decorated with the Hellenistic and Byzantine mosaics from Kos that the Italians had transferred for the purpose. The Medusa mosaic from a second-century Roman villa, the Nine Muses cycle from Kos, and a fifth-century Byzantine pavement all came as part of Mesturino's program.

After Italy's defeat in World War II, the Treaty of Peace with Italy on 10 February 1947 transferred the Dodecanese to Greece, and the formal handover took place in 1948. Rhodes had not been Greek territory in any modern sense for over six hundred years. The palace became a museum, displaying the imported mosaics from Kos that have been there since the Italian period along with armor, sculpture, and a portrait of Philibert de Naillac, Grand Master from 1396 to 1421. The medieval city of Rhodes, palace included, was added to UNESCO's World Heritage List in 1988. The bastion that Mesturino reconstructed and that the Italian engineers spent years on won a European Heritage Award in the 2010s. The building's three lives, as crusader headquarters, Ottoman magazine, and fascist holiday home, sit awkwardly together. The visitors who arrive by the millions each year mostly come for the part Mesturino made up, which they cannot easily distinguish from the parts he did not.