The gloves are off: Graffiti legend King Robbo has resurfaced to settle a score with Banksy

After meeting the man hailed as Banksy's nemesis I reckon the elusive artist is much braver (or more reckless) than I'd taken him for. Said nemesis is the Eighties graffiti legend who calls himself King Robbo. A towering giant at 6ft 8in, he's as solid as an oak tree, with his face obscured by a dark hood when we first meet. If I were Banksy I'd be quaking in my boots. And I certainly wouldn't want to upset him. Which makes the artistic spat played out between these two on London's streets, the biggest public display of artistic rivalry since Matisse and Picasso, all the more audacious.

For those who don't know, the Banksy/ Robbo saga went something like this: in 2009 a stencil artist, allegedly Banksy, went over a piece of graffiti called Robbo Incorporated, which had been left otherwise untouched on a Camden canal wall (only accessible by water) since 1985. The online graffiti community went into uproar, citing Banksy's "disrespect" and calling for retaliation. Robbo dragged himself out of a decade of retirement, donned a wetsuit on Christmas Day ("You try finding a rubber dinghy in London on Christmas Eve!"), waded into the canal and spray painted "King Robbo" in person-high silver letters beside the alleged Banksy work. Just days later the letters "Fuc" appeared in front of Robbo's "King".

A war of words, spray paint and stencils ensued in the following year, the most famous of which saw Banksy's depiction of Charles Manson as a hitchhiker holding a sign reading "Anywhere" amended to "Going Nowhere", signed by Team Robbo, and Banksy's Savemain Pharmacy mural in Essex Road tweaked so that the Tesco bag hoisted up the flagpole read "HRH King Robbo".

"I never wanted to take Banksy's stuff out, I just wanted to do something tongue in cheek. But when he put those three letters "Fuc" up, that changed things," Robbo told The Independent in his first ever interview with a newspaper.

Most people won't have heard of King Robbo, so accusations that he has cashed in on Banksy's fame and PR stunts have inevitably been levied in the two years since his exposure escalated. In the past he has been rather vocal about the integrity that his style of graffiti maintains. It is interesting then, that we meet to discuss his show at the Signal Gallery (the first of a worldwide tour), ironically titled Team Robbo: The Sell Out Tour. It is his fourth gallery exhibition. It, and upcoming commissions in New York, Paris, Milan and London, shows the growing desirability of his work, and that of other handstyle graffitists, in the mainstream art world.

Robbo's hard-man image is compounded when he tells me that his childhood was like being in the 2006 film This Is England. "I was just like the little kid in that film. It was the Seventies in east London and times were tough. I used to hang out with the big boys and they used to write their names on walls. They'd always put an 'o' on the end to let people know they were skinheads. That's why I became Robbo." It was his first taste of graffiti writing. When he was expelled from school as a teenager and went to work at his uncle's building firm, graffiti provided nocturnal escapism.

"I'd go out every night and do my graffiti. My parents couldn't understand why I did it. Why do it if there's no money in it? I couldn't explain to them that it was my passion for creating art. It was like a dopamine fix, all that adrenaline." A community of writers soon sprung up around Robbo and he became something of a celebrity among them. Pulling off the most audacious stunts without ever being arrested fuelled the chatter about his genius within his circle. His five "followers", known as Team Robbo, have worked with him for more than 25 years and he's kept them close. They will exhibit alongside him in the upcoming exhibition.

Robbo's graffiti is mostly in that abstract bubble-writing style that came out of the US in the Eighties – hence the 1984 book Subway Art is his "Bible". It is an approach that is arguably less measured than the carefully pre-prepared Banksy stencils, but Robbo's spontaneity, wit and rebellion has earned him legions of fans. His particular specialty is train writing. He's had to leg it away from British Transport Police more times than he can recall. "When it's pitch dark and there are people trying to chase you, you hone your skills really fast. It's the best art college I could have gone to."

Evidently the graffiti world is a small one. Robbo reschedules our interview to help out Ben Eine, another underground graffer-turned-art-celeb, whose print was presented to Barack Obama as a gift from David Cameron last summer. It is the smallness of this world that seems to have prompted the Banksy/Robbo spat in the first place.

"I fell out with Banksy because of respect, basically. I was introduced to him by Ben [Eine] at a party in the late Nineties. In our community it is kind of a courtesy to say you've heard of someone even when you haven't. I hadn't heard of him, but I said I had... Then Banksy said to me 'I've never heard of you.' Couldn't believe it!" he says.

Robbo responded to this slight by slapping Banksy. "I gave him a backhander. It stunned him and knocked his glasses off his face." While not the most elegant of episodes, their dispute was left at that and was simply added to the many tales of derring-do in urban folklore. That is, until Robbo's version of events appeared in print in the 2009 book London Handstyles. Robbo believes that talking about the altercation prompted a retaliation on the piece Robbo Incorporated, which was altered just two months later.

"Lots of people rang me up after [Robbo Incorporated] had been done over. They were saying, 'We'll go down there and take it out' or 'I'll get a fire extinguisher, fill it with black paint and obliterate it'. I said 'I'll have the last laugh'. But when I went and had a look at it I couldn't believe that piece of history had been extinguished."

Robbo is reticent when I ask him about the Mail on Sunday's recent (unconfirmed) report that Banksy is an ex-public school boy from Bristol called Robin Gunningham. Although Robbo knows exactly who he is, it seems even Banksy's worst enemy is not prepared to unmask him. As most of the graffiti world is populated by artists covering up their real identities ("I found out from an early age that if I used my real name I'd get caught"), this is understandable. In their game of tit for tat it is inevitable that if Robbo unmasks Banksy, then Robbo will be unmasked himself. Although, I think it is fair to say, that Banksy has more to lose by such exposure.

Will the saga go on? "Last year I decided 'enough is enough'. I'd embarrassed him, so it was time to move on... but in January he went over another of my pieces. Now he's reignited the fire I'm planning some really funny stuff for him." Banksy, beware!

Team Robbo: The Sell Out Tour is at the Signal Gallery, London (0207 6131550) to 7 May