The transformation was almost instantaneous. One minute we were on an airport train, zooming between terminals, standing beside corporate men in dark suits as they drawled into mobile phones, the next we were on an overgrown sidewalk, beside a clapboard house with a beat-up boat in the yard and a US flag hanging next to the sign, "Never mind the dog. Beware of the owner."

I had the feeling that comes when you step off the recognised trail, a mixture of excitement and apprehension, and a tiny dash of fear. All the business suits, all the tourists, all the disembarking passengers of JFK airport had got on the A train to Manhattan, but we were on a mission: to walk across New York. Our plan was to head south across Long Island, walk over the causeway that spans a network of lagoons and creeks and finish up on Rockaway, a heavily developed long and narrow sandbank off the southern coast of Long Island.

We could see it far ahead, a strip of green with some high-rise blocks rising from it. I'd arranged to stay there – well, I'd told Sophie, my partner, that I had. It was all a bit informal. On TripAdvisor, the hotels of the area – few and far between – had seemed a little intimidating. "The window had a bullet hole (.22 caliber)…" read one report. I liked the reviewer's precision, and obvious knowledge of weaponry. In fact, what I found was no less out of the ordinary.

"Is Rockaway OK?" Sophie asked. "It looks rough."

The clapboard houses ended and we started along the causeway across an inner lagoon. There were some sports fishing boats in the sheltered waterlands that almost surround the airport, part of the Jamaica Bay wildlife refuge, an important migratory bird sanctuary and diamondback turtle hatchery. I'd previously contacted the US National Parks Service about this asset of theirs, and come away with the strong impression that it was the first enquiry they had ever received – a pity, as this is a beautiful spot.

View Walking the world's megacities: NEW YORK in a larger map

As the bridge ended, at Rockaway, we encountered our first fellow pedestrian on the concrete ramp. He was wearing sunglasses, a lumberjack shirt and a nicotine-stained moustache. I asked for directions.

"Fifty-ninth Street?" He seemed surprised, but waved an arm to indicate a road we could see snaking off between houses and apartment blocks on the inner side of the beach. "Keep heading up Beach Channel Drive until you hit it. You walking?"

"Is it far?"

He made a face. "It's black."

Was that racism? Local code? "Is it dangerous?"

He reached behind himself, fumbling under his loose shirt. "Wanna take my .38?"

"No-o-o," I said, waving my hands. "Is it a bad area?"

He nodded. His hand came back from his belt empty. "That's a housing project up there – one of the worst in New York – but the gangs don't mess with outsiders. Get through it before dark and you'll be OK."

We walked, a little faster than before, up Beach Channel Drive.

"I thought you'd checked all this out?" said Sophie.

"I walked along here on Google Earth," I said, truthfully. "But you know what? They don't have little arrows pointing out people saying 'gang member'. It's something they ought to fix really."

The neighbourhood suddenly changed. At first there were Irish flags among the Stars and Stripes and the people were grizzled and white; then we passed under a railway bridge and everyone was grizzled and black. No flags. An old Lincoln Continental shot past at great speed, its shock absorbers totally gone. A youth on a bike was being pulled by a very large rottweiler. An old man sat on a step talking crazily to the world. A sign in a shop window said, "We take food stamps."

In front of an ATM that refused to give us money, Sophie suggested: "Threaten it with a .38." We asked the way again. "Walkin' to Manhattan?" laughed a man with gold teeth when we explained ourselves. "Didn't nobody tell you? New York has an excellent mass transportation system."

But, it transpired, we had arrived. On the far side of the street was a local store with a gaggle of gang members in bandanas outside. Next to it was a gateway into a small marina. This was Marina 59 and inside was the Boatel, an arts project that had somehow morphed into a louche B&B for Brooklynites on the hunt for adventure. It is certainly not for the faint-hearted: a number of semi-abandoned motor-cruiser boats, a bit of thrift-shop bedding, and a barbecue available on the pontoon.

Men were fishing off some boats. There were big apartment blocks on three sides; on the fourth a silvery reach of water led through green bushes to the lagoons. The perimeter fence looked quite high.

"Are there any places to eat outside?" we asked Connie, the woman in charge. She puffed a bit. "No one goes outside the fence after dark. I can order in a pizza."

After dark, however, the marina started to wake up. We found Karen and Zell from Brooklyn, Mike and Marie from Asbury plus a few others. It was quite a gang – sorry, I mean a group, a convivial crowd.

I went out to the store to buy beer. The real gang were inside fooling around in a loose kind of way that made me feel stiff like a sore thumb. They were actually very friendly. I loved the way they all talked, loudly and without inhibition.

"You from York?" exclaimed one young guy. "Rock on, York!" At the marina gate office I chatted to f. "Sure, we do get shooting some nights. But it's not all bad: there's good people."

Beth and Keoni employ some local youths, offering them an alternative from the near-inevitable downward spiral that starts with dealing pot. There were pictures of them on fishing boats holding huge striped bass.

A few fishermen from the neighbourhood came in: dudes sorting out their arrangements for the next day. As our own first day came to an end, we went to our berths a good deal happier than we had expected to be. I felt I had already seen more of the real NYC than most first-timers.

Day two started with a stroll across the housing project at 8am. We walked past a car with chrome skulls as fenders, then we climbed some wooden steps and the horizon threw itself back and the sky opened its arms. We were on Rockaway Beach, a fabulous seven-mile reach of sand with a proper wooden boardwalk. People were surfing. There was a yoga lesson going on. We reached a cabin selling fresh juices, coffee and home-made cookies. In 10 minutes we knew five people and two dogs.

A mile further down the boardwalk, it stopped, a sure sign of a posh neighbourhood. We soon tired of the sand and skirted inland, passing leafy Jewish suburbs. It was Saturday and the streets were busy with strolling old ladies in pearls. At Jacob Riis Park we cut further inland and got onto a huge steel girder bridge that took us into a long slog of freeways curling around back towards Brighton Beach. Indian men and Mexicans were fishing – and catching a lot.

Walking through this kind of landscape your emotions get a proper workout: elation can turn to anxiety in a second, but moments of boredom and tiredness are also brushed aside in an instant. After several hours we finally found a restaurant – actually a busy fast food joint called Roll'n'Roaster, a blue-collar family diner of epic and wonderful food – as long as it came with cheese. I was dragged away before I gorged myself to death.

And then all the voices in the street were Russian. The newspapers were Russian; the shops and restaurants were Russian. The only person who was not Russian was Adèle, our Swiss hostess, whose guesthouse I'd found on the AirBnB website. It was clean, cheap, friendly and very handy for the Russian restaurants, big dazzling Black Sea-holiday-style dining with glamorous girls and vodka.

We chose Premitskys because it was full, but as we sat down almost everyone got up and left. It took a few seconds for us to realise that they had all gone out, en masse, for a smoke.

That evening we strolled to Coney Island along the boardwalk. People were dancing on it: a transvestite with a parrot on his head, a lady with a day-glo hoop spinning around her. Was there a festival on? "Naw," she drawled, not missing a beat, "jus' another day."

The bar near the historic Cyclone rollercoaster was packed with punks, grannies, an Elvis, some truck drivers and art school students. If we'd spotted a young Bruce Springsteen or Woody Allen jotting down notes, I wouldn't have been surprised. We got back to Adèle's at midnight and fell blissfully, instantly, asleep.

Day three was a big slog up Coney Island Avenue. Afghan, Mexican, Pakistani, Jewish, Indian, then African-American neighbourhoods. We stopped to watch an artist with an easel, sizing up a clapboard house next to a brownstone block. "I kinda like the juxtaposition," he explained. "There's beauty all around here."

A long sweep through the sylvan glades of Mount Prospect Park brought us eventually down to Brooklyn's trendiest avenue: Fifth.

"Are you looking for some lunch," gushed a grand lady, unsolicited. "I'd recommend The Perch." She had lots of other advice too. "You're heading for the ferry at Red Hook? Go down President and check out Filmbiz – they sell secondhand props from Hollywood. It's kinda neat!"

We did. I refused to allow the purchase of props, especially Sex and the City stuff. My bag was heavy. Sophie had blisters now. She threw away her shoes and bought some silver glitter flip-flops. We crossed a low bridge and entered Red Hook, Brooklyn's up-and-coming zone with plenty of room to go up yet.

We were too early for the Jalopy Theatre, another hot tip, but made it to the park in time for some Latino baseball. Then, right behind the new Ikea store – the joys of Swedish furniture have come late to New York – we jumped on the little ferry to Manhattan.

This quayside was fascinating. Big old docks, many abandoned and unloved. Brando came here to research, then film, On the Waterfront. Far away across the Hudson was a tiny figure with an arm outstretched: the Statue of Liberty.

The ferry, which is free at weekends, proved to be the best possible route for our final approach, opening up big, slow views of the statue, Brooklyn Bridge and Lower Manhattan, where we landed – right at the end of Wall Street.

It was closed for an anti-capitalist demo, so we took Broadway, working our way towards Chinatown. In a park we stumbled on several hundred elderly Chinese people all playing musical instruments, a Sunday afternoon tradition apparently.

Our apartment, again through AirBnB, was on the borders of Little Italy. We didn't eat on the main strip – very crowded – but on Lafayette at a place called Osteria Morini (218 Lafayette Street, osteriamorini.com) – the sort of place, Sophie was pleased to note, that would not look out of place in Sex and the City. For me it was more Annie Hall. We were both happy.

Now we had made it to Manhattan we felt the sense of adventure slightly fall away. Everywhere was familiar from film and television. We slipped easily into the geography. It felt a little safe and comfortable. We needed a buzz.

Next day we pushed on, trekking through Central Park. Sophie's blisters were worse now. She tried going barefoot. Finally she tried my shoes. That seemed to work. We pushed on into Harlem. I wore the silver glitter flip-flops. "I can't believe I am walking into Harlem in these. I am almost certain to be mugged."

Having heard that Harlem was now gentrified, we were relieved to immediately hear sirens and spot a man in a fedora and a strawberry double-breasted suit toting a sax. He checked out my flip-flops and nodded.

On the corner of 125th Street and 8th Avenue I discussed the local arts scene with John, a television cameraman who was packing up after filming. Across the road were the red lights of the Apollo Theater, where Ella Fitzgerald, the Jackson 5, Aretha Franklin and Mariah Carey were all discovered. Jimi Hendrix won an amateur talent competition here back in 1964.

"But that was all long ago," I put it to John. "Isn't Harlem a dead place now?" He laughed out loud. "Harlem has changed, but it still kicks ass."

After checking into our first proper hotel, the boutique Aloft Harlem, we walked two blocks to the Lenox Lounge (288 Lenox Avenue, lenoxlounge.com), the area's most famous jazz club. This was where Billie Holiday sang, among many others. "Bono was sitting right here last week," the barmaid told us, "He was a real gen'leman."

I can't claim to be a jazz fan, but Harlem almost convinced me. In the orderly grid pattern of streets, like musical staves on a page, is room for an improvisational confidence that works. That evening's entertainer, saxophonist Eric Wyatt, was not the kind of avant garde maestro I'd listen to on a British radio. But here he sounded absolutely perfect.

In the interval we chatted with him at the bar. "You walked from JFK?" Eric was astonished. "I ain't never even walked across the Brooklyn Bridge."

That summed up for me the point of walking. We saw bits even the locals don't know about. We met and talked to dozens more people than we would have using subways and taxi cabs. We had not done museums or galleries. America itself is museum enough for me. We'd had an adventure.