In 272, Aurelian turned his attention to the lost eastern provinces of the empire, the Palmyrene Empire, ruled by Queen Zenobia from the city of Palmyra. Zenobia had carved out her own empire, encompassing Syria, Palestine, Egypt, and large parts of Asia Minor. The Syrian queen cut off Rome's shipments of grain, and in a matter of weeks, the Romans started running low on bread. In the beginning, Aurelian had been recognized as Emperor, while Vaballathus, the son of Zenobia, held the title of rex and imperator ("king" and "supreme military commander"), but Aurelian decided to invade the eastern provinces as soon as he felt his army to be strong enough.
Aurelian is believed to have terminated Trajan's alimenta program. Roman prefect Titus Flavius Postumius Quietus was the last known official in charge of the alimenta, in 272 AD. If Aurelian "did suppress this food distribution system, he most likely intended to put into effect a more radical reform."
Asia Minor was recovered easily; every city but Byzantium and Tyana surrendered to him with little resistance. The fall of Tyana lent itself to a legend: Aurelian to that point had destroyed every city that resisted him, but he spared Tyana after having a vision of the great 1st-century philosopher Apollonius of Tyana, whom he respected greatly, in a dream.
Within six months, his armies stood at the gates of Palmyra, which surrendered when Zenobia tried to flee to the Sassanid Empire. Eventually, Zenobia and her son were captured and made to walk on the streets of Rome in his triumph, the woman in golden chains. With the grain stores once again shipped to Rome, Aurelian's soldiers handed out free bread to the citizens of the city, and the Emperor was hailed a hero by his subjects. After a brief clash with the Persians and another in Egypt against the usurper Firmus, Aurelian was obliged to return to Palmyra in 273 when that city rebelled once more. This time, Aurelian allowed his soldiers to sack the city, and Palmyra never recovered. More honors came his way; he was now known as Parthicus Maximus and Restitutor Orientis ("Restorer of the East").