It's a bit odd that I've never interviewed Bob Mills before, given that we both frequent the same East London club every fortnight: Leyton Orient Football Club, that is. But then as Bob readily admits, he's not one for self-promotion these days, having already enjoyed his 15 minutes - well, seven years - of TV fame.

Many will remember the cult late-night clips show In Bed With Medinner, but he also co-created a genuinely groundbreaking format, The Show, wrote a critically acclaimed film, Pierrepoint (originally for Ray Winstone, but eventually Timothy Spall), as well as a Michael Barrymore vehicle that came to a sticky end.

Now happily back on the circuit but long past bothering with Edinburgh, he is appearing at a bold new alternative on August 7th: The Phoenix Fringe, which brings an impressively diverse array of comics to London's Phoenix Theatre in early August, including the likes of Alan Davies, Mark Watson and Shappi Khorsandi. And it could just be a bold new dawn for Bob.

So you're doing a show at the Phoenix Fringe, which looks a nice alternative for people not going north

I've not done Edinburgh for many years. There's been no reason to do it, you go up there to get noticed. They noticed me and now they don't notice me anymore and that's fine, I've had my time of note. But it does amaze me, when I sit and talk to the kids - anyone under 30 I call 'the kids' - and it's terrifying. Everyone goes on about student loans, 'I can't go to university'- people come back from Edinburgh ten grand in debt.

When did you last do it?

Back in the really, really early days, over 20 years ago. It's never been something that I've needed. I'm slightly different from a lot of comics, because I was married with kids before I started. So comedy's always been a job for me, unashamedly, to me it's 20 percent art, 80 percent work. The idea of doing a show with a title is anathema to me.

So how did the Phoenix show come about?

You know what, I was amazed, they phoned me up and said 'we're doing this festival, do you wanna do it, at the Phoenix?' And I know the Phoenix from [new material night] Old Rope. As it's grown and I've found out more about it I can see that it's a really, really good festival. I mean I've no idea who's gonna come, certainly when I'm on. That's the other thing nowadays, you have to self publicise - I haven't got Facebook, Twitter, haven't got a webpage. Without them now it's very tough in the world of comedy, it doesn't really affect me because people don't come to see me, I do shows where people go and I'm on it.

But things like this, I've done an email to everyone on my list, people I haven't spoken to for ten years - bailiffs, people I bought stuff from 10 years ago. I said to [the organisers] 'what am I supposed to do' and they said 'don't worry, just come and do an hour' and I thought, you know what, I might make a bit of an effort. It's only a few days away, but I think I'm gonna do something that I've always taken the piss out of, which is true stories. Over the years a lot of things have happened to me, and other comics will say to me 'you should do that on stage.' I've always said that's not what I do, my personal life has got nothing to do with an audience. But I think on Wednesday I might just say to them 'here's some stuff that has happened', and we'll see how it goes.

At least at this Fringe you aren't stuck with that show for another three weeks.

I'll do it once and that'll be it. But there won't be anyone there anyway so it doesn't matter.

Oh, I don't know, I reckon people will be intrigued to hear what you're doing these days, as you haven't toured.

Yeah, I did one tour about 20 years ago. Here's the thing, Si, when I had my time, when I done my telly - whoo, loads of telly, brilliant, but in those days there was no natural progression from being on the telly to doing a stand-up tour. Because back then people wouldn't spend £25 to see one person. They might go and see Dave Allen and Billy Connolly, but they're not going to see Joe Schmo off the telly. Whereas now you do a couple of Mock the Weeks and bang, you're on tour.

Pretty much every comic I've ever interviewed will say that they do TV to get their own tour - you seem to have a totally different mindset...

Yeah it's a funny thing, I paid £100 and went and saw Jerry Seinfeld, but generally, an hour and a half of one act is a long time. The whole point of comedy is variety.

Did you give up stand-up for a while?

I had five years off. When I was doing telly, I had a short career, about seven years, but it was very intense. I did a lot of TV shows, a lot of writing, producing. I was going to an office at 10 in the morning, I had a young family and I was earning enough, I didn't want to gigs at night as well. Although if someone had said 'on the back of this you can do a tour with a thousand people paying 30 each', fine, I would have done it. So I took a few years off, which was great, because I think I'd be blown out by now otherwise.

I never saw your behind-the-scenes chat show, The Show, but it sounds really interesting...

The Show was a weird thing. I had this moment in the sun where I'd done In Bed With Medinner and [brilliantly rubbish daytime quiz show] Win, Lose or Draw, and ITV thought 'this guy might become something - the new Paul Coia!' And they said 'do you want to do a chat show? We want something with an edge'... because Mrs Merton was out then.

So what we said was we will make a chat show, The Bob Mills Show, just like all the others, but we'll start filming at 10 Monday morning, and we'll film absolutely everything, then on Thursday we'll do the chat show, proper studio, guests, then from Thursday night we'll edit for 36 hours non-stop. And we'll put together all this. It was the most labour intensive thing you can imagine. I think we did six of them, then it didn't come back.

It sounds quite expensive...

Yeah, it was quite expensive, but I think too many people didn't quite understand it. One of the things I'm proudest of was a review in, I think, The Guardian, saying 'Bob Mills and the editor and the producer of this show have been exposed as arrogant, self-centred foul-mouthed people and the people who've made this doc have done a great service showing the callous sort of people [they are].' and it was like 'no mate, look at the credits, we made it - it's our documentary, it's not someone making a film about us...'

How real was the backstage stuff?

Totally real, that was the rule. There are some things that I'm inordinately proud of. There's a scene, dateline Thursday, 4.15, and there's me quite genuinely saying 'I'm not criticising, I'm not having a go at you, I just want to know how we've gone in four days from Tarantino to Michael Winner, that's all I'm asking, I don't think that's an unreasonable question'

If that'd happened in Hollywood, Pulp Fiction would have been a very different film.

The whole thing was like that. There's some beautiful, ridiculous stuff on it that you probably couldn't get away with now. What I like most about it is the final scene, which I'm not in, the producer and the director at a meeting at Channel 4, and the head of Channel 4 is saying 'um, I can't say yes or no about a new series - to be completely honest with you, you're on a shortlist of two, there's you and a new project by Armando Iannucci...' And the final scene is the producer and the director walking out, getting in a cab and saying 'oh well, we're fucked.' That's how the show ended.

It's ironic how Partridge that sounds, given the Iannucci connection.

Very, but what it led to was Bob Martin [the 2000-2001 ITV sitcom], because at the end I said 'this is fucking insane, filming all this and editing it all - why don't we just write it and get actors to perform it?'

Doing a Larry Sanders-style show with Michael Barrymore doesn't sound hugely promising, but it did ok didn't it?

Yeah, and then unfortunately life overtook art. Right in the middle of the second series he became persona non grata.

Ah - so there was no thought of getting someone else in, like The Thick of It?

Nah, that was it, they wanted to immediately bury him. He was airbrushed out of ITV.

You're probably best known for In Bed With Medinner - how did that get off the ground?

Ha! I was just starting out and I was working for Danny Baker, his 5Live show, I did the papers for him. Danny phoned me up saying 'I've got a new series for ITV, six one-hour slots, called World in Acton, do you fancy working on it with me, doing a bit of writing?' Nothing happened for about three weeks then my agent - I don't have one now - they phoned him up and said 'I'm afraid we're not doing that show, Danny's got a better offer at the BBC, he's left us in the lurch a little bit'

My agent, who's an old style agent, said 'you're fucked then aren't you, you've got to go to your bosses and say 'I can't fill these six one-hour slots, you're going to look a right mug - why don't me and Bob come and see you?' We went in the next day, a meeting that lasted about six hours, and at the end of it wed come up with In Bed With Medinner.

It was a very cool show at the time.

There was no money. The most expensive thing about TV programmes is studio time: we did four a night, they were half-hour shows and we only had 45 minutes for each one, so we literally did them like live shows, then put the inserts in during the edit. And for that reason you could get away with a lot of stuff, a lot of it was literally made up on the night.

It felt a bit a stand-up show, quite freeform and unpredictable...

It was the same for me, I was never sure what was going to happen. Some of it worked, about 60 percent? Which isn't bad I suppose.

So that started your TV career?

That was at LWT, I was in a ridiculous position where I had an office at LWT, and it was next to Andy Harries, and I didn't know at the time that people would sell their children to have two minutes with him: he was The Royle Family, Cold Feet man. But I used to sit in this little kitchen and make a cup of tea with him, and say 'I've come up with this idea' of Bob Martin, or Christmas Lights, the other thing I did, without realising this is gold, being able to chat with this man. He'd say 'do us a page', so I'd do him a page, 'do us an episode', whereas if you'd been an outsider you wouldn't have had any chance.

A lot of success is really just down to random geography.

It really was. Then Pierrepoint was the last thing I did.

That got a proper theatrical release didn't it?

That was a proper fillum. I'd done Christmas Lights - a lot of people have forgotten about it now, ITV was a bit in the doldrums, and this went out over Christmas and got a 57 per cent share, which is ridiculous. So I got contacted by Ray Winstone, who'd just set up his own production company, we went to have a meet, chatted all round the houses for a few hours then realised that we had a mutual love of Albert Pierrepoint.

He was Britain's top hangman?

Yep. So we wrote the script, then Ray wasn't able to do it, but amazingly Tim Spall did it... and it was fucking brilliant, I reckon. It never made any money, because ITV never having made a film for years made two at the same time, that and The Queen, which won the Oscar and the Bafta and all that. But Pierrepoint was very well received.

The great thing about that, it was kind of a full set: I've done a one-off comedy, I've done a series, I've done a film, and that's enough now. Because I was a stand-up I was able to go 'that's it now' and walk away. So that when people phone up, like they did, saying 'we've got this project, we're going to get six celebrities, and it's going to be really heavy duty alternative health cures: would you like to go to the Himalayas and drink human piss?' - that was the exact conversation, Si, I shit you not - I was able to say, you know what, 'no, I'll do 15 gigs instead'.

For details of Bob's Phoenix Fringe on 7th August show visit www.phoenixfringe.co.uk