This is mainly our modern way to look at it.
In contemporary sources, Octavian/Augustus was just a princeps among the senators of the res publica, who 'by declared intent' had 'restored the republic' and 'by accident' also held the title of imperator. Imperator in this sense meaning nothing more than 'commander' of the legions.
Being imperator itself might have come in handy in case of any opposition resorting to taking up arms against 'the man' and coercive powers much like our idealised image for an autocrat. But this option of violence was really for internal politics the less preferred method to rule — especially coming out of yet another civil war yet again — since the 'more peaceful' way lay in the powers of tribunicia potestas, forming the core of an emperor's legal means.
So in Augustus' publicised self-image and propaganda, he never was any type of monarch, so not an emperor, while in reality of course he established something just like that for which we have no better fitting modern word but: 'sole ruler'/mon-arch. In all practicality, Rome was a monarchy again, and functionally with Augustus they had a king again, but everyone was afraid to tell it like it is.
Augustus emphasised unbroken tradition and continuity, while in reality he told the senatorial ranks that they will own nothing on him in the political sphere and that they will be happy over this de facto disenfranchisement. And somewhat happy they were, with some grievances of course, since they stayed wealthy and otherwise powerful, with comparative social rank kept, but relative peace, law and order guaranteed by the new authority.
On the other hand, ancient Romans did not necessarily think of Augustus as "the first imperator" either. Roman historian Cassius Dio (died 235) for example "hailed Julius Caesar as first imperator" (Cf: — Chapter 4: Konstantin V. Markov: "Cassius Dio’s Periodization of Roman History and His Methodological Agendas", in: "Cassius Dio the Historian" doi. Also compare the relevant passages in Dio's books 44 & 53, the latter showing neatly how most of the most important 'the republic''s offices & titles, powers & rights coalesced into one new office of eventually 'emperor' under Caesar and Augustus. Republican separation of power simply ceased to be in practicality.)
The Roman political system came to define itself during the republican years as 'anti-monarchical'. So much so, that when Julius Caesar became 'dictator for life' one of the motivations for his killers was the fear that he might strive to become a rex (king). This is one of the reasons that Octavian/Augustus and his first successors avoided this vocabulary as much as possible. Rome was still a republic, 'on paper'.
So, what we primarily see are multiple shifts in meaning for certain words. Rome never again became a kingdom, as there never came any king after the 'smallish state'-time before 'the Republic'. The emperors were also called 'caesars', 'princeps', etc.
'The Romans' never saw themselves as part of 'the empire', as that English word took on its meaning much later:
mid-14c., "territory subject to an emperor's rule;" in general "realm, dominion;" late 14c. as "authority of an emperor, supreme power in governing; imperial power," in Middle English generally of the Roman Empire.
From Old French empire "rule, authority, kingdom, imperial rule" (11c.), from Latin imperium "a rule, a command; authority, control, power; supreme power, sole dominion; military authority; a dominion, realm," from imperare "to command," from assimilated form of in- "in" (from PIE root *en "in") + parare "to order, prepare" (from PIE root *pere- (1) "to produce, procure").
Whereas we see the rather succinctly put:
The Latin word imperium, referring to a magistrate's power to command, gradually assumed the meaning "The territory in which a magistrate can effectively enforce his commands", while the term "imperator" was originally an honorific meaning "commander". The title was given to generals who were victorious in battle. Thus, an "empire" may include regions that are not legally within the territory of a state, but are under either direct or indirect control of that state, such as a colony, client state, or protectorate. Although historians use the terms "Republican Period" and "Imperial Period" to identify the periods of Roman history before and after absolute power was assumed by Augustus, the Romans themselves continued to refer to their government as a republic, and during the Republican Period, the territories controlled by the republic were referred to as "Imperium Romanum". The emperor's actual legal power derived from holding the office of "consul", but he was traditionally honored with the titles of imperator (commander) and princeps (first man or, chief). Later, these terms came to have legal significance in their own right; an army calling their general "imperator" was a direct challenge to the authority of the current emperor.
— Wikipedia: Empire, Classical_period
The most important shift is of course then for 'republic' itself: from res publica ('the common good'/'the (Roman) state'), since 'the Roman Republic' was not a republic, but just that: 'the republic':
"state in which supreme or executive power rests in the people via representatives chosen by citizens entitled to vote," c. 1600, from French république (15c.), from Latin respublica (ablative republica) "the common weal, a commonwealth, state, republic," literally res publica "public interest, the state," from res "affair, matter, thing" (see re) + publica, fem. of publicus "public" (see public (adj.)).
After 'the republican times' of course, the Roman 'state' was much larger than the formerly tiny kingdom and almost fitting to the modern definition of empire. It was different enough from the almost mythical 'kingdom of Rome', or any other kingdom really, obviously, no longer 'a' republic as we would recognise it either from our modern definitions or from comparison with the reality of the ancient construct, but something new.
For this understanding of 'an empire', we do not need to resort to 'kings under the king Augustus'. There of course would be people like the Herodian kings, under the Roman emperor (up to 92 AD), or others like in Armenia, but this is not necessary for 'an empire' to be one. For Rome itself, it might be practically called 'an empire' since bang in the middle of republican times, in my view at the latest right after 'unifying' the Italian peninsula, that is conquering Magna Graeca, and getting into trouble with Carthage.
That there would be a king of kings is a middle-eastern concept superfluous to describe mediterranean situations.
How did this remarkable man convince a majority of his benevolence and rectitude? How did he prove to them that he was not ‘king’ or ‘dictator’, but princeps, the leading citizen amongst equals—and this despite the fact that there were few who did not know how much real power he held? How did he succeed in persuading members of the senate and others to subordinate their wishes and ambitions to his will? What was the reason for the enthusiasm which led people to eulogise Augustus as ‘the restorer of the Republic’, and sometimes even to want to worship him as a god upon earth? How was it that, after his death, the deified Augustus seemed to live on to become not only an object of general admiration, but also one of emulation for many of his successors?
— David Shotter: "Augustus Caesar", Routledge: London, New York, 1991.
Comparing the English word 'empire' to the Latin Imperium Romanum coming to roughly mean 'the Roman Realm' by the time of Cicero, Pompey, Caesar:
If the imperium by which the members of the senatorial elite in Rome waged war on behalf of the state was a power, almost a substance, affirmed by the gods to particular individuals, the question remains as to how this affected the way in which warfare itself was seen, and also that ultimate outcome of warfare, the Roman control of the world, the imperium Romanum. In part, as suggested above, this is a question of linguistic usage: why did the expression imperium Romanum come to be used to express 'empire' rather than the power of a magistrate or pro-magistrate?
It is worth noticing at this point that this second meaning is different in two important respects from what has been discussed hitherto: it is about only one of the two spheres of application of the imperium of a magistrate, militiae but not domi; and it is not individual but corporate, relating to the power/empire of the populus Romanus rather than of any particular Roman.
It was, of course, always true that in some sense the power of the magistrate was that of the populus Romanus, in that wherever the imperium holder was, there the power of the populus Romanus was to be found. In the case of the imperium Romanum, in the sense of 'empire', however, the identification with the respublica is much stronger and the central importance of the imperium holder seems to have disappeared almost entirely.
This second point can be seen clearly even in those rare passages in the literature of the late republic and early empire in which imperium populi Romani, used in a wider sense than simply 'power of the magistrate', includes the notion of domi as well as that of militiae. For instance, Livy can make the tribune C. Canuleius ask, when contending with patrician opponents about his bill on conubium, 'denique utrum tandem populi Romani an vestrum summum imperium est? regibus exactis utrum vobis dominatio an omnibus aequa libertas parta est?' In this context, the form of imperium, in so far as it is relevant to the argument Livy is presenting, is both domi and militiae, since Canuleius suggests the consul will call up the army to threaten the plebs and their tribune. Yet even in this deliberately heightened and paradoxical passage (Mommsen described it as 'politische Speculation, nicht technische Rede'),the question at issue is precisely who it was that held the imperium, whether it was to the magistrates or to the people that the army owed its allegiance. […]
The gens Iulia and the triumphatores of the republic formed a continuum, which had its origins in the founder of the Julii and in the king, son of the god Mars, who had first held imperium and (according to the Augustan Fasti Triumphales) first celebrated a triumph on the first day of the first year of the foundation of the city. In the midst of the forum stood a triumphal chariot, honouring Augustus himself, voted, as he tells us in the final section of the Res Gestae, by the senate, and below which was placed the tablet recording the award to him of the title Pater Patriae.
This was to be the setting in which the senate would consider the award of triumphs, from here those who went with imperium to the provinces would set forth, and it was here that, if they were successful, they would come to be rewarded with ornamenta triumphalia.
In such a context the commanders of the forces of the Roman people could not fail to realize that it was imperium militiae, passed down from the kings through the great individuals of the republic, that had made the imperium Romanum; nor indeed amid such surroundings did it need to be stated explicitly that it was from the exercise of imperium throughout the known world that monarchy had made its return to Rome.
— J. S. Richardson: "Imperium Romanum: Empire and the Language of Power", The Journal of Roman Studies, Vol. 81 (1991), pp. 1-9. jstor