In Niccolo Machiavelli's "The Prince" he says "every time the Romans moved into a new region it was on the invitation of local people". For an empire that huge it seems hard to believe, is there any truth to that?

I am not qualified to comment on Machiavelli or his works so I will refrain from trying to interpret his intent. I will focus more on the merits of the statement "every time the Romans moved into a new region it was on the invitation of local people"

This is certainly a over generalization but there are many instances where this is accurate. I will give 3 examples from the Roman Republican era to illustrate this type of behavior.

First, in roughly 290 to 280 B.C. Italian bandits, called the Mamertines (sons of mars), seized the Greek city of Messana in north eastern Sicily. When it became clear that the major power on Sicily, Syracuse, had to upper hand against Carthage in the conflict for control over Sicily, the Mamertines started to fear retaliation for their violent capture of Messana. The Syracusans were Greek and many of those slaughtered in the capture of Messana were also Greek. To Strengthen their position they appealed to a nearby Carthaginian fleet who took Messana under their protection. What happened next is a bit of a mystery, the Mamertines then appealed to a Roman garrison for protection at the town of Regium across the straights of Messana on the Italian peninsula. They argued that they, as fellow Italians with Italian religion and culture, should be friends or a protectorate of Rome. After a lengthy debate, the Romans agreed and accepted the Mamertines into their protection. A Roman garrison was sent to Messana. In response, Syracuse and Carthage, former enemies, allied together to exact their revenge on the Mamertines. This seemingly small action spiraled out of control into what was eventually the first Punic war. The first Punic war lasted from 264 B.C. to 241 B.C and ended with Rome in control over most of Sicily.

Second, in 226 B.C. an agreement was reached between the Romans and Carthaginians. A synopsis of the agreement is that the Carthaginians would not move north of the River Ebro (Spain) in arms. Around this time, the Romans took a town by the name of Saguntum under Roman protection. We do not know if this was before or after the agreement of Ebro which is important as Saguntum was probably south of the River Ebro. Whatever the case, there were pro-Carthaginian and pro-Roman factions within Saguntum and they fought each other until the pro-Roman faction found themselves in trouble and appealed to Rome for help. Hannibal, the commander in Carthaginian Spain, besieged the city in response to the Roman interference in 219 B.C. Since the town was in Roman protection the Romans demanded the siege be lifted and Hannibal arrested and turned over for trial as a criminal. The Carthaginians refused and war was declared in 219 B.C. This event eventually expanded into the second Punic war in which the Romans found themselves victorious again.

As a result of the two Punic wars, Rome found themselves in control over the entire Western Mediterranean. As this map nicely illustrates. https://upload.wikimedia.org/wikipedia/commons/3/30/Domain_changes_during_the_Punic_Wars.gif

Third, during the 2nd Punic war the Macedonian King, Philip V, made an alliance with Hannibal and became an enemy of Rome. With the Romans mainly focused on Carthage, not much was to come of this conflict and peace was negotiated in 204 B.C. This is known as the First Macedonian War.

By the late 3rd century B.C. Pergamum and Rhodes had become friends or allies of the Roman people. In 201 B.C. they revealed to the Romans that the Macedonians and Seleucids had signed a non-aggression pact threatening them and potentially Rome. Having just finished the 2nd Punic war the Romans were reluctant but voted to embark on campaign nonetheless. In 197 B.C. the Roman and Macedonian forces met in battle at Cynoscephalae. This ended in a crushing defeat for the Macedonians. The result was a peace negotiated that prohibited the Macedonians from interfering in Greece and the Aegean Sea. More importantly the Romans now considered themselves protectors of the Greeks and withdrew all of their forces in 194 B.C. Note, with the withdrawal of Roman forces the Romans did not govern of "hold" the territory. They merely brought the Greeks into their sphere of influence.

In summary, these are three brief examples of Romans expansion and conflict, all where the local people invited them to interfere in one way or another. On the other hand, there are dozens, if not hundreds, of other Roman incursions without invitation but the statement "every time the Romans moved into a new region it was on the invitation of local people" is not completely off base.

Sources: Livy, Rome and the Mediterranean; Polybius, The Rise of the Roman Empire; Good secondary source that summarizes lots of primary sources: Garrett Fagan, The History of Ancient Rome;