Left reeling: Ice fishing in North Dakota

It's 7am and 30 below on a dark February morning, and I'm driving under power lines, in deep snow, on ice. Above 145,000 acres of water. Way in the distance, the lights of the Sioux Tribe's Spirit Lake casino shimmer on the shore. I'm on my own, and I'm trying to remember to breathe.

"You want to go where?," the travel agent had asked, blinking. "Fargo," I'd repeated. "North Dakota."

"Like the movie?"

"That's the one."

The travel agent had blinked again, twirled her pen, then tentatively tapped at her keyboard. "But why would you want to go there?"

Because it's there, I could have said, like Mallory. Or I could have pointed out that, though burnt into the psyches of filmgoers everywhere thanks to Steve Buscemi and a wood chipper in the Coen Brothers' cult film, North Dakota is the US state least visited by British tourists, and isn't exactly a hotspot with other Americans.

But I had a better answer. I was going ice fishing.

Not in Fargo itself, it has to be said. In Fargo, the eastern gateway to the state, I gawped at the Art Deco signs and shopfronts along Broadway, admired the beautifully restored cinema, and drank almost certainly the best milkshake of my life: a hot fudge-and-banana malted from the reassuringly old-fashioned Zandbroz soda fountain.

I discovered that even among the general economic doom and gloom, Fargo is a fast-growing city, regularly topping America's "best places to live" rankings – and, according to one national survey, is the "Third Least Angry City" in the country. You betcha. What Fargo is not, however, is the location for the eponymous movie. Which was set in Minnesota.

Except for those road scenes. Those white-out, barbed-wire fence, flat prairie scenes – they were shot in North Dakota. And they rolled past the window for miles as I left Fargo and headed north-west, to my final destination: Devils Lake.

I breathe. Ahead, my guide John Erickstad's wheels are spinning. It is astonishingly cold, and there is nobody around. John towed another fisherman out of a snow-drift 20 minutes back, but this lake is 45 miles long and people round here don't like to crowd each other – if that were even possible.

Now I understand why we brought two trucks. John throws a thick rope over his tow bar, and instructs me in the art of pick-up truck towing; I try to look as if I'm not petrified. Back behind the steering wheel, I remember what his wife, Maria, told me at breakfast: make sure that the autolock is disengaged, and don't wear a seatbelt. It's unlikely, but just in case the ice cracks, OK?

I try to replace this uncomfortable image with the photograph, in their lodge, of 400 people – and their pickups – out on the ice for a contest. So. Reverse, pull forward, brake. Reverse, pull forward, brake. It's certainly not an easy way to go about catching some fish.

We're looking for perch. Devils Lake is famous for them; if you can't catch a perch on the lake on a summer's day, says John, well... you've got problems. Winter, it gets more tricky. You have to read the weather, speak to other fishermen, try to find out where they're biting.

Slightly more relaxed, I follow John over to what looks like Everest base camp to speak to Zippy. A regular fixture on the cable-channel fishing shows (yes, that is a plural), Zippy is a guide with the Perch Patrol. His clients, two young couples, are cosied up against the whipping winds in ice-fishing tents, toasty thanks to portable propane heaters. Tami and Scott, from Detroit, are on their honeymoon. "Because Devils Lake is the best place to fish in the Midwest," they say, both beaming, when I raise my eyebrows.

There's a grand old tradition of hunting and fishing in this part of the world. Back in Fargo, I'd visited Scheels, a two-storey sports megastore, which has 160 stuffed animals on display, including two full-sized grizzlies. Taxidermied ducks in flight hang above the aisles, directing customers to the gun racks. At the internationally broadcast University of North Dakota ice hockey game in Grand Forks, I listened as 12,000 people sang along to John Denver's Thank God I'm A Country Boy – and very much meant it.

John and I retire to his hut. Apparently you do need somewhere to get away from it all, even in the middle of nowhere; this is the garden shed on ice, complete with stove, cards, and multiple trap doors, below which sit semi-permanent ice holes.

Lined with thermal foam, – allegedly buoyant – these are dragged out in December and removed at the first signs of thaw. They can be moved if there's word of a school coming through, but mostly neighbours stay by neighbours, content to wait for the fish to come to them.

Maria shows up with cookies. She is of German descent, while John is Norwegian. North Dakota was settled by these two groups of farming migrants, who arrived early last century.

The wind blows, the gas hisses, we deal again and again. Only once does the hum of the sonar device deepen, and the little bells on the fixed lines ring. No perch, but 10 minutes of reeling produce three walleyes: dinner.

The next day, as we drive past tumbledown houses and wheatfields dusted with snow, Maria tells me how ticked off folks were that a recent National Geographic article on the state featured so many images of desolation and decay. Today, migration is to the state's cities, where the oil business, service industries and universities are doing well. It's like the movie, she says. When Fargo came out, people here were not best pleased with the actors' take on their accents. "And I just thought," says Maria, "For Pete's sake, will you listen to yourselves?"

We pull up by Mauvee Coulee; John's heard that pike are coming through. In glorious sunshine, practically mummified figures are drilling holes and setting up tents and tip-ups: spring-loaded lines that send up a flag when a pike takes the bait. One father-and-son team have a chainsaw. "Spear fishing," says John, mysteriously.

Snug in the dark tent, the lake illuminated by the sun glinting through the ice, it doesn't take long before I spy the first kill of the day. The monster noses up to the frozen minnow on the end of my line, then grabs on, hard. "Let him take it," says John. "Now pull!" Writhing and snapping, the pike fights hard on its way out. John tosses it outside; within 15 minutes, it will be frozen solid.

The fish keep coming. Just before we leave, our quota reached, John introduces me to the chainsaw man. Inside the darkened canvas, his son leans over a large sawn-out hole with something that looks suspiciously like a trident. I watch, fascinated, as a two-foot pike swims into view, attracted by a colourful lure on the end of a rod.

"Once you've got its attention, you need to aim the spear behind the gills," he explains, politely. "Would you like a go?" How can I say no? When, ever again, will I get to pretend to be Neptune? I heft the weapon, aim, and throw. The trident slices through the water and, to both our surprise, pins the poor fish to the lake floor. Both elated and horrified, blood on my hands, I emerge blinking into the sunlight. The Coen brothers, I like to think, would be proud.

Traveller's Guide: State Lines

43. North Dakota

Getting there

You can fly into Fargo or Grand Forks via Minneapolis St Paul with Northwest Airlines/KLM (08705 074 074; klm.com). You will need to rent a car to get out to Devils Lake. Another possibility is to fly direct to Minneapolis and drive into North Dakota; allow two days for the journey to Devils Lake. A third option is the train; Amtrak's Empire Builder (amtrak.com) starts in Chicago and passes through Minneapolis before reaching Devils Lake. Book through Perch Patrol (see below) for discounted train fares (starting at around £40 return from Minneapolis).

Staying there

Lakeview Lodge, 704 Elmwood Road, Devils Lake (001 701 665 5060; lakeviewlodgedl.com) has nine two- or three-bedroom self-catering apartments, some sleeping up to eight. Double rooms start at $95 (£63), self-catering.

Fishing there

Perch Patrol Guide Service (001 701 351 3474; perchpatrol.com) offers guided one-day ice-fishing packages for $150 (£100) per person.

More information

Fargo-Moorhead Convention and Visitors' Bureau: 001 701 282 3653; fargomoorhead.org

North Dakota Tourism: 001 701 328 2525; ndtourism.com

Population: 642,000

Area: Nine times the size of Wales

Capital: Bismarck

Date in Union: 2 November 1889

Flower: Wild Prairie Rose

Motto: "Liberty and union, now and forever, one and inseparable"

Nickname: Peace Garden/ Flickertail/Roughrider State