The book is divided into seven sections, which alternate in time between the beginning and midway through the period of Paul-Muad'Dib's Fremen Jihad and a period in the youth of Paul Atreides, several years before the events portrayed in Dune.
Paul on Caladan
Paul of Dune begins with the Emperor Paul Atreides Jihadi forces scattered through the Imperium, fighting the rebel houses that refused to recognize him as Emperor. While Paul visited Caladan with his mother, the Lady Jessica Atreides, and his appointed temporary suzerain of the water world, Prince Xidd Orlaq, Paul was presented with the good news that the Fedaykin have captured Kaitain. Paul immediately installed his mother as Duchess of Caladan, and departed on the next heighliner to the former Corrino capital.
Alia Reigning on Arrakis
While Paul was gone to Caladan, he left his four year old sister, Alia, as acting ruler in his stead. Alia received ambassadors from the Guild, Ertun, Loyxo, and Crozeed, who of course, begged for more melange, for the space-faring organization. Alia, wisely, told them that the Guild could have 3% more spice annually if they would contribute 200 more heighliners to Paul's Jihad.
She also watched as Korba, Paul’s chief aide and counselor, killed and dispatched the former Emperor Shaddam’s chamberlain, Beely Ridondo. The Corrino servant had gone to Arrakis from Salusa Secundus to petition the Emperor and his court, to terra-form the nuclear devastated world as he promised when Shaddam was deposed a year earlier.
The Corrino Plot
On Salusa Secundus, the former Imperial ruler, Shaddam, gave the Emperor's Blade to his Sardaukar chieftain, Zum Garon, and charted him with the task of finding his former childhood friend, the former Count Hasimir Fenring, and bringin him back to the devastated planet. Garon’s travels led him to Thalidei, on the planet Tleilax, where Fenring, his wife Margot, and their daughter Marie, were taking refuge. Garon gave Fenring the Emperor’s Blade, but Fenring replied that he would have to think about rejoining the former Emperor.
Paul on Kaitain
When Paul arrived on Kaitain, Paul allowed the former Emperor Shaddam IV's Palace to be demolished and destroyed by the over-eager Fremen, the news of which he knew would spread throughout the galaxies as a warning to rebels. Soon afterwards, Paul addressed the hastily gathered Landsraad, and informed them that tariffs and penalties will be imposed upon dissident Houses that did not bow to his will. During the banter during the question and answer session after the Emperor’s speech at the great Oratory hall; Earl Memnon Thorvald addressed the Known Universe’s assembly , and vowed to all gathered that he would nor would a great deal of others bow to another mad and misguided Emperor, and then stormed out.
Afterward, when Paul left the Lansraad gathering with Princess Irulan, Paul met his old recognized friend, the Swordmaster of Ginaz Whitmore Bludd, who was in the service of House Ecaz and was a friend to Paul's former mentor, Duncan Idaho. Bludd, who had knowledge of architecture, was asked by Paul to help him construct the grandest palace and citadel in the universe, in Arrakeen on Arrakis, to which Bludd agreed and accompanied him back to Dune.
 The Youth of Paul Atreides
The author goes back in time, to somewhere before the book Dune but after the book House Corrino. In the book, Paul is twelve years old and living on Caladan. The Ecazi-Grumman conflict has been going on for many years involving the heads of House Ecazi and House Moritani. Paul was embroiled in this famous War of Assassins conflict, during which he had to mature rapidly in order to deal with all the challenges that it possessed for House Atreides.
Paul and his mother Jessica were brought to Ecaz aboard a guild heighliner along with Duke Leto and his retinue. There, a marriage deal was concluded between Ecaz and the Atreides for Duke Leto to marry Illesa, the Archduke’s youngest daughter. The marriage was prompted by political decisions: House Ecaz needed allies to fight against the Grumman aggression, and House Atreides fitted the bill perfectly, since Leto had actively condemned the actions of House Moritani and officially formalized the Atreides-Ecaz alliance.
Duke Leto and Illesa’s wedding was to be held at Castle Caladan. Decorations included potted plants of Ecaz origin, which turned out to be concealing cleverly placed iron shards. The pots cracked and shot out these iron shards, killing a Swordmaster in the service of Ecaz, causing the Archduke to lose an arm, and causing the death of Illesa. To add insult to injury, two Moritani assassins entered Castle Caladan and tried to assassinate Paul and the young heir of House Vernius. The assassination attempt failed.
Brimming with hatred for his arch-enemy, the archduke decided to mount a full-scale offensive against House Moritani, and asked House Atreides to join him. The archduke promised to pay half of the costs of the military operation for House Atreides. The Atreides military departed on the heighliner toward Ecaz, where the Archduke realized that an upstart duke had taken over the reins of the government. Duke Leto and Duncan Idaho stealthily moved into the Ecaz palace to kill the upstart, and allowed the Archduke to re-take his homeworld and assemble his forces.
The combined Atreides-Ecaz military forces were transported to the planet Grumman. Landing, the Atreides-Ecaz forces rushed to battle against the Moritani and concealed Harkonnen forces provided by the Baron. The head of House Moritani had prepared a trap for the Atreides-Ecaz forces, but because of a foolish decision by Rabban Harkonnen, most of the Grumman and Ecaz forces fell into a deep pit which was created by detonations in underground tunnels dug many years ago by Moritani to strip the earth for ores.
Finally, a heighliner transporting Imperial Sardaukur arrived to prevent full-scale war. The whole offensive was actually grand plan by the head of House Moritani to annihilate the Ecaz, Atreides and Imperial forces together by using a doomsday weapon. The plan failed when the weapon failed to detonate as the Grumman Swordmaster Hilh Resser had disabled the weapon, finally bringing the entire conflict to a close.
 The Jihad
The book follows events during the Jihad one, four, and five years after the fall of Shaddam IV (10,194 AG, 10,197 AG, 10,198 AG) Paul's forces are engaged on multiple fronts, fighting the Houses that refuse to recognize the Atreides rule. The Fremen finally capture Kaitan, the former Imperial Capital and the homeplanet of House Corrino. Paul levels Shaddam's castle, which he hopes will be a message for the other dissident Houses. Afterward, he invites Whitmore Bludd, a former Swordmaster of House Ecaz and a friend to Paul's former mentor Duncan Idaho, to help him construct the grandest citadel in the universe on Arrakis. Meanwhile, Earl Thorvald, the nobleman who is heading the rebel forces, is being chased by Stilgar and the Fedaykin across the galaxy. Elsewhere, the exiled Count Fenring is raising his adopted daughter, Marie,on Tlielaxu to become a weapon. More and more Houses are joining Thorvald's movement due to the savage brutality of the Fremen. Bludd is executed after the Swordmaster tried to assassinate Paul to make his mark in history.The book shows Paul growing more callous and more savage as the years pass, ultimately ordering a complete annihilation of Earl Thorvald's homeplanet after he learned that the rebel was planning an attack against Caladan. At the end, Fenring unleashes his plan. While Marie fails and gets killed by Alia, Fenring manages to plunge a knife through Paul, killing him for several hours. Upon his awakening Paul does the unthinkable: he forgives Fenring and exiles him to Salusa Secundus to spend the rest of his life with his former master Shaddam, whom the Count loathes.
The following is the write-up from Dunenovels.com :
Frank Herbert's Dune ended with Paul Muad’Dib in control of the planet Dune. Herbert’s next Dune book, Dune Messiah, picked up the story several years later after Paul’s armies had conquered the galaxy. But what happened between Dune and Dune Messiah? How did Paul create his empire and become the Messiah? Following in the footsteps of Frank Herbert, New York Times bestselling authors Brian Herbert and Kevin J. Anderson are answering these questions in Paul of Dune.
The Jihad of Muad’Dib is in full swing. His warrior legions march from victory to victory. But beneath the joy of victory there are dangerous undercurrents. Paul, like nearly every great conqueror, has enemies--those who would betray him to steal the awesome power he commands. . . .
And Paul himself begins to have doubts: Is the jihad getting out of his control? Has he create
The book further chronicles the life of Paul Atreides in two different parts -- five years before House Atreides moved to Arrakis, and their involvement at that time in the War of Assassins of 10,187 AG. The second part of the book involves the life of Muad'Dib, and the immediate years after his ascension as Emperor of the Known Universe.