It is well known that the Persian Empire was divided into 20 smaller territories governed by satraps, and even Persian territories conquered by Alexander The Great kept their satraps. However, the Neo-Assyrian Empire used a similar system (400 years before the Persian Empire) with provinces and governors, meaning that The Neo-Assyrian Empire could have been the first empire with this political organization.
It possibly depends upon which definition of province one is using.
A province is almost always an administrative division within a country or state. The term derives from the ancient Roman provincia, which was the major territorial and administrative unit of the Roman Empire's territorial possessions outside Italy. The term province has since been adopted by many countries. In some countries with no actual provinces, "the provinces" is a metaphorical term meaning "outside the capital city".
If we are talking about administrative divisions outside of the capital city then ancient Egypt would have been earlier than the Neo-Assyrian Empire, and lasting longer too.
Nome, administrative division of ancient Egypt. The system of dividing the country into nomes was definitely in force by the time of the Old Kingdom (c. 2575–c. 2130 BC) and persisted with modifications until the Muslim conquest (AD 640). In late times there were 42 nomes, or provinces, 22 in Upper and 20 in Lower Egypt.
But if we are talking of provinces outside of the country, then yes the Neo-Assyrian Empire was probably the first to use such a system on a grand scale, even encompassing Egypt itself for a short period.
The Neo-Assyrian Empire (912-612 BCE) was, according to many historians, the first true empire in the world. The Assyrians had expanded their territory from the city of Ashur over the centuries, and their fortunes rose and fell with successive rulers and circumstances in the Near East. Beginning with the reign of Adad Nirari II (912-891 BCE), the empire made great territorial expansions that resulted in its eventual control of a region which spanned the whole of Mesopotamia, part of Anatolia, the Levant, and Egypt.