After the pact of Brundisium, Sextus Pompey or Magnus Pius as he called himself, son of Gnaeus Pomepius Magnus, maintained a stranglehold in Sicily and on the Roman grain supply. A short lived agreement with Antony to work in cooperation against Octavian fell apart after Brundisium, but the two triumvirs were in no position to challenge Pompey's naval superiority. By 39 BC, Pompey's fleet was near to causing famine in Italy, but rather than risk immediate hostilities, the two Roman power brokers sought to appease their hostile neighbor and cut him in on the action.
At Misenum on the Bay of Naples, the three men met to make arrangements for a peaceful end to Pompey's obstructions. While Pompey certainly thought to be included as a major player in the Roman political system, Antony and Octavian preferred honoring what would amount to honorary accolades. They offered him the Consulship for 38 BC (by this time a mostly ceremonial position), and was allowed to retain control of Sicily and Sardinia as well as the Greek Peloponnesus for a period of 5 years. His troops would receive similar retirement benefits to those of Antony and Octavian's, but most importantly, Pompey's followers, including most of the remaining Republican supporters would be scratched from the list of the proscribed and be allowed to return to Rome. With the treaty of Misenum set, Antony prepared to move east to begin his Parthian campaign, and Octavian likely sought to focus on domestic issues.
This was not to be the case, however. Within a short time Pompey complained that the Greek Peloponnesus had been essentially raped of their value prior to his arrival, though both Antony and Octavian claimed it was Antony's right to secure tax profits prior to Pompey's takeover. To insult Pompey further, his Sardinian governor defected to Octavian giving him control of that island; and in retaliation, Pompey's fleets began disrupting the grain supplies once again. Within a year of the treaty of Misenum, the peace was being quickly unraveled. Because of that treaty, however, most of Pompey's support within the Senate was gone. Republican holdouts against Octavian and Antony seemingly grew tired of Sicilian exile and with the door to return opened, joined either Antony's or Octavian's camps. Pompey, despite his position as the last bastion of the old Republican defiance, was still considered to be little more than a pirate, and his associations were increasingly anti-Roman.
Meanwhile, Octavian's status continued to rise. Starting just 5 years earlier as a virtually unknown boy simply with the luxury of being named Caesar's heir, he had risen to stand as the joint ruler of the Roman world. Through proscription, political cunning and some military bravado, he had built up a considerable amount of support both with the new and old aristocracy. Upon the return of so many exiled Senators and leading families, Octavian sought to make peace and build alliances. The day after his then current wife, Scribonia (a relation of his new enemy Sextus Pompey), gave birth to his daughter Julia (Julia and not Octavia because Octavian referred to himself as C. Julius Caesar, not Octavian), he divorced her and was impassioned by Livia Drusilla the wife of Tiberius Claudius Nero. On January 17, 38 BC, Octavian and Livia were married in an arrangement that would last an unprecedented 52 years. Though they never had children of their own, Livia's children by Claudius Nero would eventually inherit the imperial throne. Octavian, seemingly emboldened by his new found alliances, and in need to impress the population against Sextus Pompey (Magnus Pius), adopted a new name to counteract Pompey's military success. From at least 38 BC on, Octavian was referred to as Imperator Caesar Divi Filius (or General Caesar, son of a god). In so doing, he further strengthened his bond with Caesar, and pumped up his own military clout, simply through the use of a name.
Despite this posturing, as war opened against Pompey, things did not initially go well. An attempted invasion of Sicily in 38 BC had to be aborted due to poor weather, and Pompey's successful intervention. By the following spring, 37 BC, Marcus Vipsanius Agrippa, Consul and lifelong friend of Octavian, had gathered a massive fleet and trained it within an artificially enclosed harbor at Naples. Antony as well contributed 120 ships of his own to help in the cause, in exchange for the transfer of 20,000 troops to be used against Parthia. In setting this arrangement, the two renewed their alliance and made it an official form of government for another 5 years until 33 BC. By July of the following year, 36 BC, Agrippa as admiral, led Octavian's fleet in a three pronged invasion of Sicily. Two fleets sailed from Italy, and the oft-ignored Lepidus finally got back into the act and invaded from Africa.
Though there were several engagements which set back the invasion, Agrippa turn the tide at the battle of Naulochus in September of 36 BC. Using a technique to grapple Pompey's swifter more maneuverable ships, Agrippa turned the tide and utterly defeated Pompey's fleet. Pompey fled to the east and never re-established a position of strength and was eventually destroyed by Antony in 35 BC. Lepidus meanwhile had Pompey's land forces under siege on Sicily. When news of the battle of Naulochus reached Pompey's men, they wished to surrender to Lepidus but Octavian refused it. Lepidus ignored this order, however and accepted the surrender, demanding control of Sicily as a result. Octavian replied with a brilliant stroke of political strategy. Arranging in advance to bribe Lepidus men to his own side, Octavian entered Lepidus' camp and essentially stripped him of all his political value. Taking Lepidus' nearly 18 legions under his own command, Lepidus was sent into partial exile in a small Italian town, where he lived out his remaining years as a relative non-player. Though he held the position of Pontifex Maximus, which he was given upon the death of Julius Caesar, he was virtually removed from all aspects of political life. When he eventually died in 12 BC, the title of head priest of the Roman Religion passed to Octavian (by then Augustus) and it forevermore was passed to each emperor in turn. At this point in 36 BC, the Triumvirate was officially over, leaving Octavian as the sole ruler of the west and Antony in the east, and though issues were settled for the time being, the monumental clash was inevitable.