The men sat in the front row of EasyJet flight 5443 from Gatwick to Budapest were wearing sunglasses and sheepish expressions. A fellow passenger caught their eye. "Are you guys in a band?" she smiled. "Yeah," sighed Maxim Reality as he glanced across at Liam Howlett and Keith Flint, a man who doesn't find it easy to look inconspicuous. "We're The Prodigy."

A look of recognition flickered across her face and the band shrugged, just a little self-consciously. Like the fine men and women of the British Music Press Corps scattered about the plane behind them, they were on their way to Sziget, a weeklong Hungarian festival which bursts into life every August on an island in the Danube nestled between the once distinct cities of Buda and Pest.

It was a Friday, and we knew that the festival had already started without us. The main stage which The Prodigy were due to play that evening had already been headlined that week by Prince, Pulp, The Chemical Brothers and a Hungarian 'pop rapper' trading under the name 'Gringo Sztár'.

When the call had come through from The Quietus on Monday they had expressed their regret that we wouldn't be able to cover the Prince show, but I felt that there might be a story which would, like most things, be bigger than the purple midget of pop. I'd been tuned into the news, and I'd been reading Chomsky: "In Hungary, the neo-fascist party Jobbik gained 17% of the vote in national elections, perhaps unsurprising when three-quarters of the population feels that they are worse off than under Communist rule," he wrote earlier this year. "The rise of neo-fascist parties in much of Europe would be a frightening phenomenon even if we were not to recall what happened on the continent in the recent past. Just imagine the reaction if Jews were being expelled from France to misery and oppression, and then witness the non-reaction when that is happening to Roma, also victims of the Holocaust and Europe's most brutalized population."

"What are your thoughts on Gogol Bordello?" I'd asked the editors. If The Quietus wanted someone to explain the importance of Sziget, I felt we needed to talk to people from Europe's most brutalized population. I'd interviewed Eugene Hütz several years previously and we'd discussed a documentary, The Pied Piper of Hützovina, which he'd made about his travels among the Gypsy musicians of Eastern Europe. In a time when European politics is lurching to the right, he could provide some insight into what it meant that a handful of Hungarians were managing to stage a sprawling, liberal, pro-gay, feminist, internationalist music festival with a tent dedicated to Roma Gypsy music. They'd agreed, and four days later I'd found myself on a plane trying to avoid making eye contact with Keith Flint as I waited to use the toilet.

At the arrivals gate at Budapest airport I met the rest of the Press Corps and our generous festival hosts presented us with a choice: after checking into our hotel, we could either be taken directly to the site to ensure that we received our recommended daily dose of Dizzee Rascal, or we could be flown, individually, over the site. This is not the sort of offer that I am made very often and it sounded, well, bonkers.

A couple of minibus rides later I found myself in a field being introduced to my pilot, Kristöf, and his plane, a Cessna 172. Without further ado he took me up to make a series of low bombing runs over the island, close enough to confirm that the singer from Skunk Anansie is definitely still bald. It proved an innovative way to familiarise myself with the scale and layout of the site, eschewing the old-fashioned and frankly now out-dated 'map' option, but I could have done with a drink to distract me from the flashing 'TERRAIN ALERT: TOO LOW' display on the dashboard. The cabin service was negligible.

I finally arrived at the festival at around 9pm, just in time to catch the end of an unscheduled fracas between the police and a handful of indignant skinheads. Gyula György Zagyva, an MP from Jobbik, the party Chomsky called "neo-fascist", had been attempting to make his way into the festival site accompanied by around 70 of his Nazi goons, ostensibly and inexplicably in order to protest against petrol prices. The subtext, as it was explained to me by an enthusiastic and extremely apologetic young Hungarian, is that they wanted to scream their hate-fuelled gibberish at Gypsies, Jews, immigrants and foreigners and that they despise Sziget because it stands for all that is right and good and true in the world. The protest itself was dispersed quickly and efficiently, and did not unduly trouble my festival experience, but the very fact that Nazis feel the need to protest at the gates is a clue to just how damn important a cultural bulwark Sziget is.

I made a note to investigate this further, but by this point a powerful hunger was upon me. We headed towards the 'Hungaricum Village', described in my crumpled press release as a place where "the traditions and peerless values of the Hungarian countryside come to the fore." The traditions and peerless values of the Hungarian countryside, it turns out, are fuelled by an enticing dish of 'Rooster Testicle Stew'. I was impressed. In the annals of menu composition, 'Rooster Testicle Stew' is one hell of an opening gambit. I knew that The Quietus would expect total coverage. The barmaid reassured me that this was no comic ruse to fool tourists. "Don't worry," she said, "they taste just like liver."

She passed me my meal, and I noted that roosters have unexpectedly substantial testicles, but also that you still need a hell of a lot of them to make a bowl of stew. I learned later that they also have primarily internal sex organs, so if I take anything from this experience it's the discovery that cocks don't actually have cocks. I found myself somewhere to sit while the men from Q and NME proved themselves to have more conservative tastes. Quelle surprise. The barmaid was right, rooster testicles do taste just like liver, but it's the springy, slightly rubbery texture that makes it hard to forget you're eating balls.

We flashed our press credentials and made our way into the VIP area to watch The Prodigy. There is something stirring about watching several thousand Europeans simultaneously lose their shit, and The Prodigy are by now practiced experts at making this happen. In a strange way they share a birthday with this country: they've been making music for their jilted generation since 1990, the same year Hungary hosted its first free elections of the post-communist era. To my disappointment, the opportunity to sing 'Happy Birthday' never presented itself.

By the time the last reverberations of 'Out of Space' had finished echoing around the arena the crowd looked brutalized, and so did the rest of the Press Corps. When they boarded the hotel-bound minibus, our photographer Veronika and her husband, both Sziget veterans, offered to take me to find the Roma Tent. I had an idea that this would be the heart of the festival, and expected a Gypsy knees-up, but actually what we found was a mellow drunken waltz being played by Romanian cimbalom player Giani Lincan.

We repaired to a nearby bar to drink shots of a fizzy vodka called Fény, served from a vintage soda syphon, and local favourite Unicum. Shots cost about the same as a draft beer, 530 forints (£1.70), and a cocktail costs about 1000 forints (£3.20), which goes some way to explaining the international appeal of the festival, especially as tickets for the full week start from 140 Euros (£122). The shortfall from tickets is made up by sponsorship – some 25% of festival revenue is from corporate sources, and it was striking how 'branded' parts of the site were. Converse and Vodafone logos dominated many of the arenas, and incredibly there was even a McDonalds on site. Frankly, I'd rather eat a bowl of testicles. I lost Veronika and her husband and eventually found myself dancing, or at least awkwardly twitching, to Kode9 who was playing in what appeared to be an abandoned aircraft hangar at the centre of the site. Sometime around 3am I remembered that I had to get to a hotel in central Budapest, so I staggered to the ferry port. The nighttime journey by boat down the Danube was, at least to my recollection, spectacular. The Hungarian Parliament Building is surely one of the world's great architectural feats, and Sziget is blessed to have Budapest as a perpetual headline act.

Saturday morning announced itself in a blaze of awful heat. My mouth, as Kingsley Amis once wrote, had been used as a latrine by some small creature of the night and then as its mausoleum. I was somewhere in Budapest's 'castle district'. My eyes burned, but I could just about make out the shape of our tour guide as he produced a cartoon rooster on a stick and held it above his head. He grinned: "We don't want anybody to get lost, so everyone must follow my cock!" It was, I realised, going to be a long morning.

I read somewhere that parts of Buda Castle date back to the 14th century and that under King Sigismund Luxemburg it became perhaps the largest Gothic palace of the late Middle Ages before being further developed by King Matthias, Hungary's great Renaissance leader. Our guide focused on more recent intrigues. "This is where Katy Perry shot her video for 'Fireworks'," he told us. Matthias, who was after all the King of Bohemia, would no doubt have been delighted by the idea of pop musicians shooting fireworks from their tits down through the ages. In the 1950s Buda Castle was gutted by the new Communist regime who considered the Royal Palace a symbol of decadence. Our guide paused again: "This is the Hilton hotel, where Paris Hilton came to launch her perfume." No wonder so many people say they were better off under Communism. "Now," he herded us together again, "who wants to hold my cock?"

We were back on the island in time for the festival's international media press conference. Gabor Takacs, one of the organisers, cheerfully announced that this year 385,000 people attended Sziget, which translates to about 77,000 on any given day. Around 80% of those were foreigners – many of them Dutch and Italian but also around 2,000 Brits – making it perhaps the continent's biggest pan-European party. In total, Sziget this year attracted visitors from 55 different countries and hosted bands from 43.

Fruzsina Szep, who programmes the festival, spoke about the importance of promoting and protecting the distinct cultural identities of Eastern Europe: "I go around quite many festivals and to be very honest I have never seen a tent at any other festival dedicated to Roma culture," she said. "We have tried to invite more artists from our neighbouring countries to represent their culture at Sziget. This year we also established the Eastern European Funfair, where we tried to bring back the 60s and 70s when Hungary was still… well, not everything was allowed. Now we are at a festival so we have tried to create a venue which has an historical flavour but which is still joyful and fun."

The Eastern European Funfair is something which really could only exist at Sziget. A mock Communist-era fairground designed with the intention of reminding the crowd what life was like for their parents and grandparents growing up behind the Iron Curtain, yet rendered with a sort of soft-focus nostalgia. The organisers themselves, of course, grew up in what must now seem like another world. Gabor told me that he was 18 when the Communist regime fell, and when I asked him whether he went to festivals in the previous era, he laughed. "We had Pioneer Camps. We just went and sat around campfires. It was nothing like this!" He gestured around at the drunken revelers staggering between stages. "With Sziget, we are trying to do something that wouldn't have been possible when we were teenagers," he told me, "the essence of the concept is that you're free to do anything." They are liberals and immensely proud of their festival's internationalism. I asked them if, given the rise of right-wing politics in Hungary, they see the success of Sziget as a kind of ideological statement. "No, no ideology," he said, and I realised then that they handle that word with a great deal more care than I do. "An anti-ideological ideology, then?" I suggested. He laughed. "Yes, that's more like it."

I wanted to know more about the Nazi protests on Friday night. It turns out that there's a long history of opposition between Sziget and Hungary's far-right. Several years ago, upset about the success of Sziget, neo-fascist groups set up their own alternative festival called Magyar Sziget – 'Sziget' means 'island' in Hungarian, 'Magyar Sziget' means 'Hungarian Island'. Bafflingly, despite hating Sziget in part for it's internationalism, Magyar Sziget now attracts fascists from across Europe. The fascist imitation is widely seen as so pathetic in its desire to foster political extremism that earlier this year Britain's own tinpot totalitarians the BNP fired their London Regional Secretary, Chris Hurst, after he was photographed in attendance.

The Sziget organisers explained all this with a sort of sighing resignation that they have to put up with these lunatics in order to throw their party. As I'd heard on Friday, this year's trouble stemmed from the fact that a neo-fascist group had called their protest inside the festival site and then had the temerity to complain when security failed to allow them in without tickets. This seems to have been thought up as a cunning wheeze, designed to get them some easy publicity, possibly free access to the festival and potentially an excuse to bring yet another in the series of crank litigations with which they enjoy clogging up the Hungarian courts.

It's a shining testament both to the appeal of Sziget as a festival and to the endless tolerance of the organisers that, according to Hungarian news reports, when it became clear their protest ruse wasn't going to work, many of the Nazis just bought day-tickets and disappeared into the site. With a bit of luck they'll have ended up in Sziget's specially designated 'hugging tent' at 3am and their lives will have changed forever.

Fruzsina then introduced me to Kása Béla, a musician and photographer who has spent decades chronicling Gypsy music. He gave me his own perspective on the influence of Roma culture on Hungarians like himself: "I first went to Transylvania in 1973. It was the first time for me to discover that there was music other than Jimi Hendrix and The Rolling Stones, and although I like that music very much, this really spoke to me." I walked with him back to the Roma Tent, whose walls are adorned with his photographs of various generations of musicians. "It is hard to describe the importance of Gypsy music to Hungarian music," he said. "There are so many gypsies living in Hungary and Transylvania and a lot of them make their living as musicians. It is the same in India, in places like Rajasthan. They are fantastic players but they do not learn in school or classes but from their parents and grandparents. The Roma Tent here now draws performers from so many countries: Hungary, Romania, India, Macedonia, Poland, Serbia…"

Indeed, music seems like an ideal entry point to a culture which is more often caricatured than understood. As Garth Cartwright wrote in Princes Amongst Men, the story of his journeys through the Balkans with Gypsy musicians: "How to break through such entrenched clichés? Music. Music has always been the Roma area of absolute excellence, as essential as human speech and just as precious."

By the time I got back to the main stage the Press Corps informed me that I'd already missed Kate Nash's impromptu beat poetry, so, trying not to feel too despondent, I headed out in search of something I'd never heard before. On the contemporary Hungarian stage I saw the Erik Sumo Band, featuring a lady with the unlikely name of Kiss Erzsi, play a pop set built around the sort of funk bass that gives a visceral shake to the old laryngeal prominence. They were followed by Hiperkarma, an earnest indie band, but Marcell, a fan of theirs, assured me they have excellent lyrics. He also tipped me off about a handful of Hungarian bands worth investigating: Besh o droM, Quimby and Tankcsapda.

Later, I passed by the Kaiser Chiefs singing their impressively self-aware meta-anthem 'Everything Is Average Nowadays', before I arrived in a disability park where I was encouraged to take a wheelchair out for a spin. Moments later, a man on a zip-line whistled over my head, and when I looked up I realised there was a fully-functioning bar suspended from a crane – although I gave up on drinking there when I looked down and saw the length of the queue – there were only 20 seats, and everybody got their 20 minutes in the sky. At some point later on I stumbled across a spectacular theatre performance which included acrobats soaring over the audience with fireworks propelling them by their boots, and eventually came to the belated realisation that all the good stuff was going on amongst the trees well away from the branded arenas. The night seemed to culminate when I watched a transvestite sing 'Rehab' as a tribute to Amy Winehouse, who had originally been booked to headline the main stage that night.

I blinked and it was Sunday morning and I was poolside drinking Tequila Sunrises with the man from Q. I had just stepped out of an 80°C sauna, into a freezing plunge pool and then into a bar. If the aesthetic beauty of Budapest provides a perfect headline act for Sziget, then the fact that they have the Széchenyi Thermal Baths on their doorstep seems almost like cheating. The springs which supply the pools come out of the ground naturally heated to over 70°C. God's own bathwater.

What better way to follow that than with Mariachi El Bronx? The crowd lapped up their music in the appropriately scorching heat while I had another Tequila Sunrise and tried to start a rumour that they're fronted by Herc from The Wire.

Despite being listed as an American band, Gogol Bordello were welcomed onto the main stage as local heroes returning from overseas conquest. They attracted one of the biggest and most boisterous crowds of the festival, and Eugene Hütz, who sang mainly in Russian, delighted in instigating a series of ever-widening circle pits. The formation of a circle pit in a tightly-packed crowd is an incredible thing to be a part of, and the way that a couple of people working together can coordinate a whole group into opening up a space in which everyone can dance and move freely seemed at that moment to serve as an elegant metaphor for Sziget itself.

After the explosion of energy for Gogol Bordello, The National seemed like a lull in proceedings. They're capable of making beautiful music, but at Sziget they came onstage to a spontaneous round of apathy and promptly set about earning it. I decided to leave them to it and headed backstage to find Eugene Hütz, who I'd heard was about to give a press conference.

Without wanting to disparage my colleagues in the European Music Press Corps, the gathering did not get off to an auspicious start. The opening question, from a Hungarian journalist, was: "Are you still friends with Madonna?" Hütz, to his credit, refused point blank to answer: "Next question?"

More interesting territory was explored on the subject of local hero Béla Bartók, the composer who Hütz described as: "The Sonic Youth of Eastern Europe." "His music was a reinterpretation of all the information he had encountered," he explained. "It was very punk rock, very atonal and powerful and energetic. It inspired me to take the music from Eastern Europe and make my own music out of it, just the way Béla Bartók did."

Hütz spent much of the press conference arguing that it is in the small towns and villages of the region where real innovation has happened: "In Russia and the Soviet Union, or ex-Soviet Union, ethnical rock, or gypsy punk, or ethno-rock is essentially a peripheral phenomena. It's something that all capital cities now try to cash in on, and of course there are big Balkan and gypsy parties in every big capital in the world now, but the truth is that bands like Krambambula come from Belarusia, one of the God-forgotten parts of the Soviet Union. There are other republics, but that's where all the ethno-punk rock originated. I always want to bring things back to the realisation that ethno-punk rock does not come from Moscow or Leningrad or St Petersburg, it came from Belarus, Ukraine, Turkmenistan and all these fucked-up republics that had nothing going on besides their own ethnic roots and a bit of The Rolling Stones and Sex Pistols on the airwaves. That's the real combination and it's a lot more powerful than fashionable people in the capital cities."

When I eventually managed to grab him to talk about people's attitudes to Gypsy music, he told me a story about a recent gig in Romania which illustrates the schizophrenic nature of contemporary bigotry: "Before the show I was playing a CD with a mix of my favourite songs and while there was a Romany song, from Romania, the whole audience stood up, like 80% of the audience, and were booing, basically shouting that 'Gypsies must die'. Then, of course, they greatly enjoyed our concert afterwards! There was a cool review in the newspaper the next day that said: 'The Romanian audience is so fucking dumb they probably think 'Gypsy Punks' means 'Fuck the Gypsies'. That's how dumb the shit on the street is, but if you go to the streets of Bucharest the only posters that get any attention are for the Hungarian Gypsy Orchestra, Gypsy Kings and fucking Gogol Bordello! Then you have all that dumb shit going on at the same time."

He emphasised the importance of places like Sziget: "I feel like the organisers of this festival in particular are almost like an antidote to the rest of the façade of Hungary, and other Eastern European countries like Romania and Ukraine. Because they are curators they're a little bit deeper in their insights into what matters in a culture. Of course, if you go and ask people on television, or on the radio, or on the street, they will despise anything inspirational as a nuisance and disturbance," he says. "Of course, people who are moving in arts circles understand the significance of dissolving that and that's why they make things like the Roma Tent here. Much respect to them."

Much respect to them, indeed. I worked my way back into the crowd for the final night of something that looks and feels just like a music festival, a performance space and an adult playground, but which is also part of the battleground for the soul of Europe. It is a place which embraces political and social freedoms and a barricade against those who would seek to divide populations and preach hate. Sziget is a monument to the first and best political instincts of rock & roll: This festival kills fascists.