Simon's novel begins with a man sitting in a bar in an unnamed Spanish city. Facing him, on the other side of the plaza, is a bank. The man remembers how during the Spanish Civil War he had stayed in a hotel, the Palace of the title, which was on the same site as the bank, but which has since been destroyed. Other memories follow: of an Italian met on a train who had described to him an assassination he had once carried out; of a funeral of a socialist politician, witnessed from the balcony of the hotel; of a hot, sleepless night spent in one of the hotel bedrooms. The memories recur obsessively, each time in a slightly altered form, and the novel moves backwards and forwards in time, between the man's past and present. The first chapter is entitled 'Inventory' and the last 'Lost and Found'. Between these two attempts at stocktaking, the man considers the events that might have changed his life, but fails to identify them. The youth who stayed in the city during the Civil War and the man drinking at the bar are related only as the hotel is to the bank.

All the characters in the novel have a shadowy existence. They are not individualized by names, but are referred to throughout by the sort of labels one might use to indicate a stranger. There is the American, the Italian with the gun, the schoolmaster, the man wearing what resembles ...