Paul Bruce Dickinson was born in Worksop, Nottinghamshire. His mother, Sonia, worked part-time in a shoe shop, and his father, Bruce, was a mechanic in the army. Dickinson's birth hurried the young couple, then just teenagers, into marriage. Initially, he was brought up by his grandparents; his grandfather was a coal-face worker at the local colliery and his grandmother was a housewife. This is referred to in his song "Born In '58" from the album Tattooed Millionaire.
Dickinson started school at Manton Primary in Worksop while his parents moved away to Sheffield. Soon afterwards, when he was six, he was also despatched to Sheffield, where he attended a primary school in Manor Top. After six months, his parents decided to move him to a small private school called Sharrow Vale Junior. Due to constant moving, Dickinson states that this period of his life taught him to be self-reliant as he was unable to make close friends. Dickinson has a younger sister, professional showjumper Helena Stormanns, who was born in 1963. He tried to isolate himself from her as much as he could when he was young, supposedly out of spite because she, unlike him, was a planned pregnancy and birth.
Dickinson's first musical experience was dancing in his grandparents' front room to Chubby Checker's "The Twist", when he still lived with them in Worksop. The first record Dickinson recalls owning was The Beatles single "She Loves You", which he managed to persuade his grandfather to buy him, which made him more interested in music. He tried to play an acoustic guitar belonging to his father, but it blistered his fingers.
By the time he moved to Sheffield, Dickinson's parents were earning a good living from buying property, refurbishing it and then selling it for a profit. As a result, much of Dickinson's childhood was spent living on a building site, until his parents bought a boarding house and a bankrupt garage where his father began selling second-hand cars. The income from their business success gave them the opportunity to give Dickinson—then 13 years old—a boarding school education and they chose Oundle, a public school in Northamptonshire. Dickinson was not opposed to moving away from home because he had not built "any real attachment" to his parents, having been raised by his grandparents in Worksop until he was six.
At Oundle, Dickinson was picked on and routinely bullied by the older boys of Sidney House, the boarding house that he belonged to, which he described as "like systematic torture" and meant that he became an outsider. His interests at Oundle were often military; he co-founded the school wargames society with Mike Jordan, and he rose to a position of some power in the school's cadet force, with which he was allowed to handle live ammunition, which he used to create explosions as booby-traps.
Oundle was where Dickinson became attracted to hard rock, after hearing Deep Purple's "Child in Time" being played in another student's room. As a result, the first album he ever bought was Deep Purple's In Rock, which created his interest in rock music. After In Rock, he went on to buy Black Sabbath's debut, Jethro Tull's Aqualung and Tarkus by Emerson, Lake & Palmer. Every term, a band would play at the school, the first of these which Dickinson saw was called Wild Turkey, featuring former Jethro Tull bassist Glenn Cornick. After that, he saw Van der Graaf Generator and Arthur Brown.
Dickinson initially wanted to play the drums, later obtaining a pair of bongo drums from the music room for practice. He remembers playing "Let It Be" with his friend Mike Jordan, during which Dickinson discovered his singing voice while encouraging Jordan to sing the high-notes. Shortly afterwards Dickinson was expelled from Oundle for participating in a prank in which he urinated in the headmaster's dinner.
Returning home to Sheffield in 1976, Dickinson enrolled at King Edward VII School, at which he joined his first band. He had overheard two other pupils talking about their band and that they needed a singer and so volunteered immediately. They rehearsed in the garage of the drummer's father, and the band were impressed by Dickinson's singing, encouraging him to buy his first microphone. Their first gig took place at the Broadfield Tavern in Sheffield. Originally called "Paradox", the band changed their name on Dickinson's suggestion to "Styx", unaware of the American act with the same name. They made local newspaper headlines when a steel worker was awoken by their performance and tried to smash the band's drum kit. Soon afterwards the band split up.