There was a strange sensation leaving Rio de Janeiro, a feeling that sat somewhere between relief and gratitude. The carnival had been everything we expected and nothing we could have prepared for. It was a whirlwind of feathers and sequins, of sweat and samba, of bodies moving as one through streets that throbbed with life. We emerged from that experience blinking into the daylight, lucky to be alive and in good health, clutching our memories like precious jewels. Brazil had embraced us, squeezed us tight, and then released us back into the world. Our flight to Lima was mercifully uneventful, a quiet pause before the next chapter of this grand adventure. We had scheduled a few days in Peru's capital, just to catch our breath and take the temperature of this new country.

I had booked us a little place online. Three stars, I believe it said. Now here is a valuable travel lesson I learned in Lima: star ratings are not a global currency. Three stars in Lima means something entirely different to three stars in, say, Skegness. To say the hotel was basic would be to insult the very concept of basics. It was a concrete coffin, a room without windows, a space that seemed designed by someone with a deep and abiding hatred of fresh air.

There was no wardrobe, no television, no air conditioning. The room boasted double height ceilings, which sounds grand until you realise the only thing they achieved was to make the single fan, perched precariously high on the wall look like a nervous bird, and was by all accounts completely useless. High up, just below the ceiling, were decorative gaps in the concrete, little slots that were supposed to encourage airflow around this interior community of rooms. Our only view of the outside world, and singular source of ait, was through the door, which had built-in wooden window panels. But these openings were without glass, so opening them meant you looked directly into the communal hallway. Privacy at this point is moot point as this meant that you were now on view to everyone  walking past.

We abandoned our concrete sanctuary and ventured out into the city. Lima presented itself as a bustling metropolis doing its best to accommodate the traveller and the local in equal measure. Old ladies sat on street corners selling sweets from little plastic tubs. Street vendors pushed carts offering sandwiches or, with rather more graphic immediacy, skinned lambs or ducks hanging from hooks. The architecture told stories of a wealthy colonial past. Intricately carved wooden balconies overhung the streets, fretworked boxes where the wealthy once watched the world go by, built during a time when land taxes were calculated by square footage on the ground. If you couldn't build out, you built up and over. It reminded me of Stratford upon Avon. Clever.

Near the grand Plaza Mayor we stumbled upon the haunting and beautiful sight of the Tapadas Limenas. These were mannequins dressed in the traditional costume of the veiled women of colonial Lima. The outfit was extraordinary. A tight fitting silk dress called a saya, and then a long dark veil, the manto, worn over the head and face in such a way that it covered everything except for one single eye. Just one eye, exposed to the world. The effect was both deeply mysterious and utterly provocative. Imagine the freedom of that. Hidden behind that veil, a woman could move through the city, could socialise, could flirt, could engage in political intrigue without ever being recognised. History tells us that husbands would pass their own wives in the street without a flicker of recognition. The Church condemned it as scandalous, of course, but for the women of Lima, it was a superpower. One eye, gazing out from behind history, and for 300 hundred years they held onto that power.

After two days of Lima's chaotic charm, we flew to Cusco. The flight alone was an adventure. Pookie gripped my hand tightly as our small plane swooped between mountains, descending towards an airport runway that looked comically short. The wings seemed close enough to high five the adobe houses on the hillsides as we passed. An interesting fact for you: Cusco's Alejandro Velasco Astete International Airport is often cited as one of the most challenging in the world for pilots due to its location in a valley and the high altitude, which significantly affects aircraft performance. You feel that fact in your stomach as you come in to land.

A taxi wound through the narrow streets and deposited us at our hotel on the Plaza Regocijo. We were hungry and Lima's culinary offering had been, let's say, forgettable. But Cusco was a different story entirely.

The food was fantastic, a revelation of flavours we hadn't anticipated. We sat on the balcony of the Casa Carbajale, wrapped against the sudden chill, eating dishes that warmed us from the inside out. The thin air was immediately noticeable. We were now at 3,400 metres above sea level. Every step felt like a small negotiation with the atmosphere. Street vendors offered Viagra or Coca Tea to help visitors with the altitude sickness. We looked up treatments on the internet and it advised not to drink alcohol for the first 2 days above 2500 metres.. we decided it was already too late for us and so ignored it. We also found out that Acetazolamide would help so we ventured into a pharmacy and bought some. We invested in some thick woollen ponchos, transforming ourselves into cheerful, multi coloured llamas, and climbed aboard an overnight bus to Puno, by the shores of the magnificent Lake Titicaca (3812 metres).

The bus dropped us in Puno as dawn broke over the altiplano. We walked, slowly and carefully, to the harbour where a small boat waited to take us to the floating islands of Uros. The boat meandered through narrow channels in the vast reed beds, the totora reeds standing tall and green around us. And then we saw them. The islands. They floated on the lake like giant golden baskets, bobbing gently on the surface. We stepped onto one and the ground moved beneath our feet, a soft, springy sensation like walking on a waterbed made of straw.

The Uros people have lived on these man made islands for centuries, building their homes, their schools, their entire world on a thick bed of reeds that must be constantly replenished. They showed us how the islands are built, layer upon layer of cut reeds stacked on a floating root base. They told us of the lake's size, the highest navigable lake in the world, and the history of their people who took to the water to escape the expansion of the Incas on land. We were glad of our ponchos now. Despite the bright sun the wind swept across the lake, cutting through us, and the altitude made standing still feel like mild exertion.

From the floating islands we boarded another boat, this time heading for the island of Amantani. As we approached, a cluster of women in traditional dress waited on the shore. A local woman, small and sturdy with a smile that crinkled her eyes, greeted us and gestured for us to follow her up a muddy trail. Now, I consider myself reasonably fit. I was an athlete once. But carrying both our bags up that hill, trying to save Pookie from a tumble on the slick path, I was reduced to a panting, wheezing steam train. My lungs burned. The air at over 3900 metres is thin. Very thin. The general recommendation for acclimatisation is to fly to a high place and then only ascend a few hundred metres per day. Yet here we were, four days after leaving a beach in Brazil, puffing our way up an Andean mountainside. Pookie, to her credit, concentrated entirely on putting one foot in front of the other, her face a mask of pure determination.

Our host's home was simple, constructed from mud bricks and a corrugated iron roof. She ushered us inside and, after we had recovered the ability to speak, served us a dinner of hot, nourishing soup with quinoa and vegetables, accompanied by fresh pita style bread cooked on a clay stove in the small dark kitchen area. It wasn’t the most delicious meal we had eaten in Peru but it was very satisfying. We ate in the warm glow of their kitchen, surrounded by a family who had opened their home to strangers, and then as night fell, we crawled into our beds, utterly shattered.

Morning on Amantani was a revelation. The sky was a sharp, crystalline blue. The air was cold and clean. The views from the island across the vast lake were simply stunning, so clear, so untouched. Pookie had a go at weaving with our host, sitting on the floor in front of a traditional loom and trying to master the rhythm of the threads. She looked wonderful in the colourful traditional dress they lent her, a radiant splash of colour against the deep blue of the lake beyond. We walked with the family into the small town-square, where the local people were gathering. They treated us to a traditional dance, the music simple and repetitive, the movements joyful. Some of the other travellers, those who had taken more time to acclimatise or perhaps just had better cardiovascular systems, decided to climb the last 100 metres up to the top of the island's highest hill. They wanted to see the temple at the summit and offer something to the gods who live up there. We watched them go, gave them a wave of encouragement, and promptly ordered a cool drink in the square instead.

We were led down to the small island harbour and were supposed to be collected here and taken to another island, but our boat never arrived. We waited, watching the lake, watching the sky, watching our fellow travellers depart on their journey. No boat. With no phone signal and Spanish limited to little more than hello and thank you, we were starting to wonder if we would become permanent residents of Amantani. Eventually, our homestead host flagged down a passing boat from another company. The captain, seeing our predicament, happily agreed to take us. He took us via a different island, giving us an unexpected bonus tour, and even fed us a simple lunch of fish and rice on the journey back to Puno. Kindness, we have found, is the most common language in the world.

Another overnight bus carried us back to Cusco, where the staff at the Hacienda Hotel greeted us like old friends returning from a long journey. One night back in familiar surroundings and we were ready for our next adventure. This time we boarded a much nicer bus, a proper touring coach, and headed into the Sacred Valley.

Our first stop was Pisac. At the entrance, and generally roaming around looking for food as if they owned the place, were dozens of alpacas. They stood there with an expression of serene superiority, chewing endlessly on what looked like nothing, their enormous liquid brown eyes watching us tourists with what I can only describe as gentle contempt. Some were pure white, others a rich caramel brown, and a few were the colour of charcoal, their fleeces so thick and fluffy they looked like they'd been dressed by a particularly enthusiastic costume department.

One particularly bold individual, clearly the self appointed welcoming committee, wandered right up to Pookie and began sniffing her poncho with great interest. She stood perfectly still, delighted and terrified in equal measure, as the creature decided whether she was a friend or a potential snack. It eventually concluded she was neither and wandered off to pester a German man holding a bag of corn kernels.

Perched high on a mountain ridge, the agricultural terraces of Pisac spiral down the hillside like giant green steps. An interesting fact: the name Pisac is often said to derive from the Quechua word for partridge, "pisaqa", because the layout of the settlement on the mountain is shaped like a partridge. The stonework here was older, more rustic than what we would see later, built by earlier civilisations whose techniques were still being refined. But the views into the valley below were breathtaking, literally, as we were still at considerable altitude. The Urubamba River snaked through the green floor far below, a silver ribbon connecting the dots of villages and fields.

From Pisac we continued to Ollantaytambo. And this was a complete transformation. This was not rustic. This was a masterpiece. The skill and craftsmanship required to make the enormous stones of the Temple Hill fit together so perfectly was unbelievable. Each stone was a giant polygon, carved and shaped to lock seamlessly with its neighbours. The gaps between them are millimetre perfect. You cannot slip a piece of paper between them. A guide pointed across the valley to the cliffs on the opposite side, explaining that the stones had been quarried up there, dragged down, across the river, and then up this mountainside. The very idea that man could do such a thing without modern machinery, without the wheel even, is magical. It is mind blowing. The Templo del Sol, with its curved wall of monumental stones, could not be easily recreated today without ridiculously sized machinery. And to consider the terrain it sits on, the steep, unforgiving hillside, makes the achievement feel almost supernatural. I stood there in total awe.

Another long day was drawing to a close. We boarded a train that wound its way through the narrowing valley, following the Urubamba River as it tumbled over rocks, until we reached the town of Aguas Calientes. This is a bustling little place, a huddle of hostels, restaurants and market stalls set up almost exclusively to cater for the pilgrims heading to Machu Picchu. It sits right next to the roaring river, crammed into a steep valley, all steps and narrow lanes. We checked into our hotel, a perfectly adequate room with windows that actually opened, and went in search of dinner.

The main offering in Aguas Calientes appears to be pizza. Every other restaurant has a wood fired oven and a menu of Italian classics. But Pookie, ever the culinary adventurer, has a radar for the unusual. She spotted a small place called Full House and on their menu was the famous Peruvian delicacy: guinea pig or Cuy. I tried a small piece. It was fine. A bit like chicken but with a darker, gamier flavour. But I was glad I had chosen the salmon. Pookie persevered and ate most of it, declaring it tasty but far too bony to be a satisfying meal. Too many tiny ribs, too many little feet. She said it was like eating a chicken that had been through a mangle. The fact that they served it in a little jacket and with a hat on made it all the more curious.

But it was time to rest. Tomorrow, we would rise early and finally visit the place we had come so far to see. The lost city of the Incas. Machu Picchu. Please join us next time for that incredible trip, and for the long journey back to Grenada, a journey that would take an unexpected detour via the white sands of Barbados.