King of the road: John Walsh marks Bob Dylan's 70th birthday with a trip down Highway 61

Bob Dylan turns 70 this week – and the road that inspired one of his best-loved albums remains as seductive as ever for those drawn to the heartland of American music: the Deep South

It's late on a sultry May night in Clarksdale, Mississippi and, in the Hambone Gallery, before a small audience, three men are playing the blues. One is gently chording an acoustic guitar, the second plays in a traditional blues style, fingers walking up and down the neck like a lifer patrolling a tiny cell; the third is a virtuoso, playing high up on the neck, firing off showy trills and weeping glissandi that leave us watchers open-mouthed. There's no stage here. The floor is bare. The musicians sit on the gallery's bleak wooden chairs.

It's a low-fi rock performance, some way from the sonic mayhem of Iron Maiden at the 02. And that's how the inhabitants of Clarksdale like it. Here, in the poorest region of the poorest state in the Union, the blues were born like this. Before heavy metal, before the ego-monstrosity of stadium bands, before rock'n'roll itself, the blues started life with individual black musicians wrenching wails and cries from bashed-up instruments in front of small, rapturous crowds.

The guitar virtuoso, Sean Appel, bearded yet baby-faced (he could be Seasick Steve's rubicund grandson) puts his Gibson in its case and chats to the audience about his town. "This is a magical place. You can meet people here in their eighties and nineties who knew John Lee Hooker! I'm telling you. Honeyboy Edwards, he's 96 years old, he played with Robert Johnson, and you can see him in the street!"

Clarksdale is on "Blues Alley", a 196-mile section of Highway 61 that runs from Memphis to Vicksburg – and on and on, in both directions, down to New Orleans and up to Minnesota. It's the road that took black Mississippi fieldworkers away from slavery, north and south into major cities where they could improve their lives – and the road that spread the blues across America, as the migrating masses carried the music with them.

The highway was celebrated by Bob Dylan on his sixth album, Highway 61 Revisited, full of blues songs of travel, threat and desolation. The road was important to him. It runs through Duluth, Minnesota, where he was born, and Hibbing, Minnesota, 75 miles away, where he grew up. Its symbolism as a road to freedom is clear. In his autobiography, Chronicles, he explains:

"[When young] I was into the rural blues as well; it was a counterpart of myself. It was connected to early rock'n'roll and I liked it because it was earlier than Muddy and Wolf. Highway 61, the main thoroughfare of the country blues, begins about where I came from... I always felt like I'd started on it, always had been on it and could go anywhere from it, even down into the deep Delta country. It was the same road, full of the same contradictions, the same one-horse towns, the same spiritual ancestors... I was never too far away from any of it. It was my place in the universe, always felt like it was in my blood."

To mark Dylan's 70th birthday, on 24 May, I decided to travel down Highway 61, to see what can be found there a century after the early bluesmen were born. I started in Memphis, pulling into town during a Biblical cloudburst. The Madison Hotel, when I found it through the curtains of rain, was a haven of dirty martinis and high thread-count sheets, but I had to wait for the dried-out morning to see Beale Street ("The Home of the Blues") in its sunlit finery.

The second most visited street in the US after Bourbon Street in New Orleans, Beale was home in the 1900s to segregated Memphis's black culture, its banks, barbers' shops, clubs and shops. WC Handy, a Clarksdale trumpet player brought in by the mayor in 1903 as a music teacher to a local band, wrote "Beale Street Blues" in 1916, and from the 1920s to the war, every black musician, from Louis Armstrong to BB King, came to pay tribute.

The Memphis Rock 'n' Soul Museum at 191 Beale will give you the history, along with a moving evocation of sharecropper life in 1920s Mississippi. Beale Street itself, however, is now two blocks of tourist stuff between 2nd and 4th Street. Rum Boogie Café will serve you delicious barbecue ribs, the Strange Cargo shop will sell you made-in-Korea, guitar-themed shirts for $50, but the crush of sightseers might put you off.

You'd be better off visiting Sun Studios. Easily spotted by the giant guitar over its front door, Sun heard the first notes of rock'n'roll. In 1953, a handsome dude from Tupelo came in and asked if he could record a Connie Francis cover for his Mom's birthday. His surname was written in the book as "Prestly". In the tiny recording booth, you can stand where Scotty Moore, Elvis's guitarist, stood when they recorded "That's All Right" during a late-night jam, and started everything off.

You must visit Graceland to check out, not just where Elvis lived for 20 years, but to see what passed for good taste in the 1960s. The piss-elegant glassware and table settings! The African-bush décor of the living-room! The billiards room with the miles of pleated material on the ceiling! Stand in the Graceland kitchen and try not to think of him ordering the toasted peanut-butter-and jelly loaf that killed him.

But you must get out of museums and on the road. I loaded up the Chrysler convertible and headed south. The road was dead straight, the fields on either side as flat as Norfolk and, as I travelled, they became soggier and soggier, the recent rain gleaming in the drills with a strobe-light effect. A few miles out, I passed the hamlet of Walls, home of "Memphis" Minnie and "Fiddlin' Joe" Martin – every one-horse town can boast some six-string nickname.

The hamlets of Dundee and Lula flashed by as we entered writer territory. Here's Rich, Mississippi, where Thomas Harris, author of Silence of the Lambs, was born; and Jonestown, from where Richard (The Sportswriter) Ford hails. Between them is a tragic landmark: the spot where, on 26 September 1937, the car in which Bessie Smith was being driven to a gig collided with a truck. She died, aged 43, on the way to hospital. It was claimed that she died because a white hospital denied her admission.

Here is Coahoma, birthplace of Charlie Patton, a weedy-looking, nine-stone half-breed from Dockery's Plantation who had (according to Howlin' Wolf) the voice of a lion, and who could, in the 1930s, play the guitar behind his back like Hendrix, or between his legs, like Chuck Berry. And here at last is Clarksdale, the heart of the Delta, where everyone of any consequence in Blues-land either came from or eventually came to: Sam Cooke, John Lee Hooker, Son House, Ike Turner, Big Jack Johnson, Junior Parker – and a melancholy-looking guy called McKinley Morganfield, who became known to blues history as Muddy Waters.

I drove past indifferent clapboard houses, broken sidewalks and 7-Eleven stores, turned down a country lane and found the main street. I was looking for the Ground Zero Blues Club (its address, helpfully, was 0, Blues Alley) and here it was – a two-storey brick warehouse, seemingly disused and run-down, with doors and walls entirely obscured by graffiti. Outside the front door, a sofa and two chairs offered minimal comfort; but the rusting boiler and bits of machinery on the stoop didn't seem welcoming. The door was locked. The side walls looked impregnable as Fort Knox. Just as I was thinking of finding a motel, my saviour arrived – Miss Tony, a short, cheery innkeeper, who brought me local pecan beers and showed me my room for the night. It was a suite, full of authentic 1950s furniture (in the sense that it's been there since the 1950s), and a mile-wide bed with swishy black dancers holding up the bedside lamps.

Down in the bar, the thick impasto of graffiti spreads across the counter, the pool tables and the stage, where Jimmy "Duck" Holmes or Robert "Wolfman" Belfour would be playing old delta blues later tonight. This is as real as blues venues get. Beale Street's idea of "authenticity" is a Hard Rock Café. This is the real deal. Ground Zero is internationally renowned, co-owned by the actor Morgan Freeman, an "entertainment executive" from Memphis called Howard Stovall, and Bill Luckett, a tall, Goethe-quoting construction mogul and attorney, now running for the governorship of Mississippi.

Luckett and Freeman met in the mid-1990s, when both were involved in residential property, and became friends. They noticed how many tourists in town were asking about where they could hear live music.

"About that time," Luckett told me, "this Englishman and a Dutch guy got in touch and said they wanted to start a blues club in Clarksdale. And I thought, are we gonna leave it to people from England and Holland? This place" – he waved his hand at the graffiti-riddled monstrosity behind him – "was the Delta Cotton and Grocery Company, which had stood empty for 30 years. Somebody was gonna have to pull it down or do it up. I thought, well, we were looking for a blues club..."

The penny dropped. He and the others bought it for $1 a square foot and set about renovating it in four months – only to distress it shortly after opening. "On the first night, an attractive lady climbed on the bar and said she wanted to reserve a place for her feet. So we drew a back mark around them. Other people wanted to join in, and soon there were bodies lying on the floor..."

Ground Zero's fame spread. Elvis Costello came a-calling, and Paul Simon, and Chris Stein from Blondie. Robert Plant (who made an album with Jimmy Page called Walking Into Clarksdale) came with his two sons. "And who's that British comedian who drives a taxi – William Fry?" Stephen Fry? "That's the guy. He came and sat on this very sofa." Luckett isn't keen to change the town much. "Someone described Clarksdale as 'gritty' and we like that," said Luckett. "It's an old-style town, with no central square and not much new construction downtown. We don't wanna turn it into Fort Lauderdale. 'Keepin' it real' is our slogan."

The dark secret at the heart of the blues is displayed at the crossroads where Highway 61 meets Highway 49. Above a small traffic island, an installation of three guitars hangs in the air. It's a tribute to Robert Johnson, an artist about whom little is known; but everybody in Mississippi knows what he's supposed to have done. He was born in 1911 in Hazelhurst, Mississippi, and went to work in the cottonfields in Robinsonville while still a boy.

At 17 he married his childhood sweetheart, Virginia, but she died in childbirth. He turned to music for solace, learnt to play bottleneck guitar, and performed in juke joints alongside Sonny Boy Williamson and Charlie Patton. By all accounts he was rubbish; people would complain about the racket he made.

Then one night he walked to the Clarksdale crossroads, recited an incantation and summoned the Devil to come from hell and inspire him. The devil appeared and tuned his guitar – and thereafter Johnson played like a demon, fast and tight and menacing. His songs were recorded from 1936 by the American Record Company – but he didn't have long to enjoy fame. In August 1938, he died after drinking whisky poisoned by the jealous husband of an old flame. Three different grave sites outside Clarksdale proudly bear his name. "Crossroads Blues" became a classic, later recorded by Cream, Jimi Hendrix – and Bob Dylan.

Clarksdale isn't a pretty town, but it's fascinating to walk round. Down the main street, at 262 Delta Avenue, the Cat Head Delta Blues and Folk Art is unmissable. The brainchild of a young blues enthusiast called Roger Stolle, it's a shop where you can buy arcane blues recordings and discover who's playing where that night: Stolle is a fount of knowledge about juke joint one-offs and upcoming gigs. His book, Hidden History of Mississippi Blues ($20) brings the ancient bluesmen to life, often in their own words. If you're tired of cheeseburgers, seek help in the Madidi restaurant (also owned by Morgan Freeman), Clarksdale's only nod to fine dining. You can toy with baked oysters or frog's legs, and follow them with the "Featured Entrée" – ie The Only Main Course – which is usually filet mignon.

Back on Highway 61, I passed no-horse towns called Alligator and Duncan, wondered whether a diversion to Rosedale was worth a look, just because the village is namechecked in a Robert Johnson song; and passed Shaw where Honeyboy Edwards, now in his nineties, is the local hero. At the intersection with Highway 82 is Leland, which had a reputation in the 1940s as crammed with drinkers, gamblers and bootleggers. The more civilised headed for Ruby's Night Spot, presided over by Ruby Edwards, whose big personality drew Elmore James, Howlin' Wolf, Muddy Waters, BB King and Little Milton to her bar-stage. Today, there's an end-of-party feel to Leland, but the Highway 61 Blues Museum has a fine collection of moody photographs from its heyday; and the town has commissioned murals by a dozen artists to celebrate local stars, who include the albino guitarist brothers Edgar and Johnny Winter.

Once you've passed through Hollandale, home of the Chatmon family, one of the most celebrated dynasties in Mississippi, you're leaving Blues Alley. Below Rolling Fork, Highway 61 changes appreciably. The fields are suddenly lush with woodland. You'd swear some money had been spent on the infrastructure. It has. You're heading for Vicksburg, where a famous 47-day siege in 1863 marked the turning point of the Civil War, and where federal money still pours in every year to maintain several thousand US army corps engineers and scientists.

You can check out the conduct of the siege at the enormous National Military Park and stay at the Anchuca Historic Mansion and Inn where the four-poster beds are astounding, the food delicious and the welcome from your hosts, Tom and Chris, hearteningly warm.

More antebellum ("before the war") houses are the principal attraction at Natchez, 80 miles south, a beautiful, scrubbed-up southern belle of a town on the swollen Mississippi, best approached down the leafy highway of the Natchez Trace. My favourite house was Monmouth Plantation, a dream of white pillars, water features and leafy orchards, where Union soldiers were billeted during the war. You can feel the breath of Scarlett O'Hara in the bar where the flamboyant barman, Roosevelt, will knock up a potent mint julep of his own sinister devising.

Highway 61 will take you on down to Baton Rouge and New Orleans, where the music becomes Cajun zydeco and the landscape takes on tinges of French and Spanish. But it feels as if you're getting further away from the heart of the highway, around Clarksdale. For all its ragged, juke-joint feel, the town is the uncompromising birthplace of the blues, and the highway is the concrete river which took that music north and south, turning it into jazz, rhythm and blues, and rock'n'roll. No wonder Bob Dylan felt so intense about it. Drive 100 miles down Highway 61 and you too will feel you've always been on it, and could go anywhere from it.

Travel essentials: Deep South

Getting there

* The writer travelled with Lastminute.com (0871 222 5969), which offers return flights from Heathrow to New Orleans with Continental from £657; and double rooms at the Doubletree by Hilton, New Orleans from £98 and at the Crowne Plaza New Orleans and Crowne Plaza Memphis from £99, room only.

* Continental (0845 607 6760; continental.com) flies to New Orleans from Heathrow via Houston.

Getting around

* Holiday Autos (0871 472 5229; holidayautos.co.uk) offers a week's car hire starting at £135.

Staying there

* Madison Hotel, Memphis, Tennessee (001 901 333 1200; madisonhotelmemphis.com). Doubles from $307 (£205).

* Delta Cotton Company Apartments, Clarksdale, Mississippi (001 662 645 9336; groundzerobluesclub.com).

Apartments from $95 (£63).

* Anchuca Mansion, Vicksburg, Mississippi (001 601 661 0111; anchucamansion.com). Doubles start at $138 (£92).

* Monmouth Plantation, Natchez, Mississippi (001 601 442 5852; monmouthplantation.com). B&B starts at $217 (£145).

Visiting there

* Hambone Gallery, Clarksdale (001 662 253 5586; stanstreet.com).

* Memphis Rock and Soul Museum (001 901 205 2533; memphisrocknsoul.org).

* Rum Boogie Café, Memphis (001 901 528 0150; rumboogie.com).

* Sun Studio, Memphis (001 800 441 6249; sunstudio.com).

* Graceland, Memphis (001 901 332 3322; elvis.com/graceland).

* Ground Zero Blues Club, Clarksdale (001 662 621 9009; groundzerobluesclub.com).

* Cat Head Delta Blues and Folk Art, Clarksdale (001 662 624 5992; cathead.biz).

* Madidi, Clarksdale (001 662 627 7770; madidires.com).

* Highway 61 Blues Museum, Vicksburg (001 662 686 7646; highway61blues.com).

* Vicksburg National Military Park (001 601 636 0583; nps.gov/vick).

More information

* Deep South USA: 01462 440784; deep-south-usa.com