It’s not often you’ll hear the words “Genghis Khan slept here,” and okay, that isn’t exactly what our guide is saying – it wasn’t Genghis Khan, but rather one of his descendants. Still, the guy clearly had some fearsome DNA. My friend Shawn and I have just ascended to the Amber Fort outside of Jaipur on the back of a psychedelically painted elephant – touristy but worth-it fun – and now we’re touring this onetime stronghold of the Raja Man Singh I, a hilltop city complex overlooking a lake.

Rajasthan is full of structures like these – remnants of the maharajas, or kings, who once ruled here – and of the Mughals, who invaded in the 16th century. The state boasts vast riches of gems, precious metals, marble and decorative arts and crafts (all of which you’ll have numerous opportunities to lay down rupees for). Even the name means “land of kings.” While the maharajas of today have had turn their fantastically ornate homes into museums or hotels to handle the hefty upkeep and taxes, the traces of Rajasthan’s incredible wealth and history glitter on, spectacularly.

The great news is that seeing all this in royal fashion – getting chauffeured around, sleeping where the nobles and emperors slept and sampling the dishes they ate – can run you as little as the same amount of time at some all-inclusive sand-and-sun resort. And while this dream trip won’t be quite as relaxing as a week on the beach (India’s pace is frenetic and its roads harrowing, even as a passenger), it’s a hell of a lot more exciting and culturally eye-opening.

You’ll probably end up flying to Delhi, like we did, since it’s the closest international gateway to the region. India’s capital lacks sufficient charm to make up for being a sprawling megalopolis of 16 million, but as long you’re here, you might as well see a few things. Old Delhi – a crumbling, once posh maze of fascinating narrow streets – is dirty, frantic and very exciting. It’s home to Chandni Chowk bazaar, which attracts shoppers from all over the region for its variety and bargains. (Of course, getting said bargains as a foreigner can be somewhat tough, but do your best to negotiate hard.)

In the thick of Chandni Chowk’s Muslim area near the Jama Masjid mosque, you’ll find Karim’s, a venerable institution for tandoori-grilled meats and breads (one of the highlights is seeing the ovens in action as you walk in), which makes an excellent pit stop for lunch.

If you can spare a day, or a half-day, sign up for a tour with Dhruv Gupta of Old Dehli Bazaar Walk and Haveli Visit. Gupta has an MBA from Cambridge and works as a management consultant, but his true passion is the neighborhood where he grew up and where he’s meticulously restored his family’s haveli (historic home). In his company you’ll get access to things a tourist wouldn’t otherwise: some of the neighborhood’s loveliest hidden lanes, men raising pet pigeons on the roof of building, a shop peddling incredibly detailed and expensive wedding invitations, excellent snacks from beloved shops and a simple vegetarian dinner in his family haveli. His tours cost $50 for a half day and $100 for a full day, and proceeds go to the haveli’s upkeep.

Other Delhi highlights include the formidable Red Fort – where you’ll hear for the first but not the last time about the mightily Mughal Shah Jahan, and the Ghandi Smitri, the pleasant bungalow that was the great man’s home for the last few months of his life. There you can see, among other things, the spartan worldly possessions he left behind: a knife, fork spoon, eyeglasses and little else.

Some of the vegetarian dishes of northern India.

Don’t miss dinner at Minar in Connaught Place – I had several Delhi residents gush to me that this is the best Indian food anywhere. Forget about calories as you dig into these heavy North Indian specialties: irresistible fried chicken pakora, exorbitantly creamy butter chicken and thick, dark dal makhani, mopping it all up with your choice of breads and washing it down with Kingfisher lager. Then jump in a taxi and head south to the newly jumping nightlife district of Haus Khas village, a winding strip in South Delhi that’s a favorite with the area’s young professionals. If you have any room left, you can get cocktails and bites at O.T.B. and follow it up with dancing at Zo.

In the morning, it’s time to hit the road – you’re not in Rajasthan yet. A travel agent can help book trains and buses, but a package that includes a car and driver plus lodging is a popular way to see Rajasthan, since distances are far and transit schedules can be inconvenient if you don’t have tons of time. Rajasthan is also a popular domestic tourism destination, so many things book up during the high season from October to March (it’s also wedding season, and one such event can sell out an entire hotel). You can contact a tour company from abroad or visit a travel agent in Delhi – choose one affiliated with the official Delhi tourism board for the best rates.

For a luxurious experience at a still-affordable price, India by Car and Driver, the company I went with after a friend’s endorsement, offers customized chauffeured tours: you can specify which cities you’d like to visit, and how many nights in each place, or ask them to put together an itinerary. The cost of your tour will depend on the kind of car you choose and whether you specify budget, mid-range or luxury accommodations. Unless you specify otherwise, it will also include an English-speaking guide for the monuments (something more independent types might want to forgo as tours can drag on) and certain extras like an Udaipur boat ride.

At the mid-range, it’s possible to stay in any number of the heritage hotels, onetime palaces and noble homes, found all over Rajasthan, which start at about $50 or $60 a night for a double room. While these places lean more luxury-circa-quite-a-few-decades-ago than super plush, they make it up for this with gorgeously ornate decor and abundant character, plus the knowledge that you’re turning in where a maharaja – or at least his daughter – once slept.

Of course any journey between Delhi and Rajasthan should include the Taj Mahal, in Agra, just two-and-a-half-hours’ drive from Delhi on the new Yamuna Expressway. The photos don’t do it justice – the world-famous building is the mausoleum Shah Jahan (there he is again) built for his favorite wife, Mumtaz Mahal. Viewing this tomb, you can sense the grand love story that motivated its construction: its rises, airy as marshmallow creme, from its chateau-rivaling grounds by the Yamuna River.

If you leave Delhi in the morning, you’ll arrive in time for lunch in Agra and an afternoon Taj visit – stick around for the magical sunset. There’s also a morning train from Delhi to Agra – use a travel agent to book ahead since it tends to fill up. Spend at maximum one night in Agra; the town has little to offer beyond the Taj and its architectural predecessor, the beautiful Itmad-ud-daula tomb, or “Baby Taj.”

Holy cows.

The following morning, it’s finally time to cross into Rajasthan. Leaving the Taj, you might opt to stop at Fatehpur Sikri, an abandoned city constructed by the great Mughal emperor Akbar, who’s remembered for, among other things, his ecumenical approach to religion – he created a belief system that combined Hindu, Muslim and Christian teachings (a wife from each faith didn’t hurt his broad-mindedness). A quick zip is all you’ll need to see his poorly located city-in-the-middle-of-nowhere, which reflects all of these architectural styles.

If you’re traveling by car, skip the air-conditioned tourist-trap restaurants and ask your driver to stop for lunch at one of the rustic dhabas, or truckstop restaurants, that line the highway. These anti-frills establishments are one of the purest no-bullshit pleasures of traveling in India, offering cheap, filling vegetarian fare, and, for tourists, opportunities for fun interactions with rough-and-ready truck drivers or local families packed 10 or 12 to a vehicle – a good chance to practice any Hindi you’ve picked up.

Our driver, Ajit Kumar, talked several dhaba owners into offering Shawn and me impromptu cooking lessons, where we learned the basics of North Indian vegetarian cooking: a lot of oil, coriander, red chili and turmeric, plus onions, garlic and green chilies, form the base of most dishes.

You’ll find many familiar items like palak paneer, soupy dal, aloo gobi, as well as some more local options including kadi, a yogurt curry thickened with lentil flour. Soak it up with hot, freshly grilled chapatis, which will keep on coming until you cry uncle. A meal for three might run five or six bucks.

Ajit nimbly navigated terrifying highways, chatting to us about Indian culture and customs all the while, and throwing in some surprises including, over the course of a week, opportunities to feed a whole menagerie of animals: pigeons, monkeys, fish and, of course, the ubiquitous “holy cows,” which have the right of way all over this country, no matter how big the city. “Good karma,” Ajit would announce each time, and I found myself believing him, or wanting to as we sped down roads and highways, dodging oncoming cars passing slower vehicles and narrowly avoiding head-on collisions on several occasions. “Don’t worry,” Ajit assured us. “I’m the best driver in India.”

By afternoon you’ll be in Jaipur. With 4 million residents, Rajasthan’s capital isn’t exactly a charming small town, but it is photogenic, thanks to the famous pink walls (actually, they’re more terracotta-hued) of its old city. Check into whatever heritage hotel you’ve opted for – even if you’re used to budget traveling, these are a worth-it splurge, especially if you’re splitting the bill with another person. Samode Haveli is a gorgeous, and luxury-priced, option right near the old city, while Diggi Palace, slightly farther out, boasts sprawling grounds, an on-site farm and the opportunity to take a culinary workshop.

Allot some time to wandering the pink-lined streets, snapping photos of the Pepto-Bismol-colored buildings, including the many-windowed Wind Palace. You might be sold hard on the tailoring in Jaipur – custom suits in India go for less than $200 – but I found that the tailors in more-cosmopolitan Udaipur had a better sense of contemporary fashion.

Rajasthan, a land of creative facial hair. 

In the evening, head to the 6:30 Bollywood showing at the famous Raj Mandir Cinema, a throwback movie house that’s retained its glamorous 1970s flair – all mirrored walls, fanciful ceiling, and dramatic lighting. General admission is just 130 rupees, or slightly more than two bucks. There’s just one film option, usually shown in Hindi, but half the fun is listening to the crowd scream and cheer during high-tension moments. If you’re totally lost, you can always leave at intermission.

The next day, get up early to visit the Amber Fort, outside of town. The queue for elephant rides (offered until 11 a.m. only) moves quickly, and it’s worth the photo-ops, not to mention the silly fun, to ride a plodding pachyderm to the top of this mountaintop city. Once there, dodge the hucksters peddling trinkets and do a quick breeze-through of this fortress – there are more spectacular buildings to come.

One of these is Jaipur’s City Palace, where you can see, among other interesting things, an exhibit about Maharajah fashions through the ages. It’s also worth popping into the nearby Jantar Mantar, which houses, among other things, the world’s largest sundial. Have lunch at Ram Dhaba for a taste of malai kaftan, balls of paneer in a spicy gravy.

It’s time to move. If you won’t be heading all the way west to Jaisalmer, consider doing a camel safari in Pushkar. This small desert town is a holy Brahmin city known for its lake where pilgrims stop to pray and bathe (should you opt to do some praying yourself, be prepared for both an interesting cultural experience and being skillfully guilted out of a generous donation). The town itself is far from holy, an idyll for hashish-smoking backpackers, which caters to this type with shops selling hippy-dippy garments and restaurants offered varied cuisines, including Mexican and Italian.

Word is Jaisalmer’s desert is more vast and remote, but I enjoyed my one-night camel adventure with Dharma Camel Safari, which included an afternoon ride past villages and dunes and yellow mountains to our desert camp, where the friendly teenage guides cooked a meal of local vegetarian specialties – daal boti masala, balls of wheat bread meant to be dipped in dal – over a wood fire. After we slept early under a sky so dense with stars I couldn’t even find the Big Dipper, there was a slight delay for sunrise chai while one boy ran over to the next-door farm to collect freshly squeezed buffalo milk. By 9 a.m., after an hour’s ride, we were back in town.

You can keep heading west from here to Jodhpur, painted blue to Jaipur’s pink. We were short on time, so instead we cut south to Udaipur, passing miles of marble dealers along the way as the landscape grew more mountainous. After hours, and another terrific dhaba lunch, we dipped into a green valley – Udaipur. I imagined the way this desert oasis must have looked to travelers of yore, galumphing along dusty roads astride their camels. Even in a chauffeured SUV, it was a relief to reach the lake town that’s often called India’s most romantic city.

My only regret about Udaipur was not spending more time there – but we had a flight to South India to catch, and other parts of the country to see. For this typically budget traveler, the Lake Pichola Hotel seemed impossibly posh. Its grand lobby sparkled with colored glass chandeliers, and the rooftop bar and restaurant looked straight at the glorious City Palace on the other side of the river. Our deluxe room had a balcony just off the lake. Except for the Rajasthani menu and clientele of stylishly dressed Indian diners, I would have thought I was in Europe.

Though we were reaching the end of our patience with “monuments,” as people refer to all of Rajasthan’s numerous forts, palaces and the like, the City Palace, a Winchester Mystery House of royal digs that’s been added onto by countless maharajas over the centuries, was nothing short of breathtaking. The maharani and her family – now on the 24th royal generation – still reside in part of the palace, and they’ve turned another section into a museum. Inside you’ll find an enclosed garden and swimming pool and the fabulously ornate private quarters of a past royal couple – judging by the mirrored bedchambers of a bygone maharani, she would’ve been right at home in the disco era.

In the afternoon, we managed to shake our septuagenarian guide and set out for a wander of Udaipur’s twisty streets, passing cows and colorful houses, and even a group of women dressed in brilliant saris herding donkeys saddled with bags of rocks. In India, it’s quite common for people to chat you up on the street, either to sell you something or to practice their English – often both – so were weren’t surprised when a friendly man named Kadir, a Kashmiri Muslim whose family had emigrated from Afghanistan many decades ago, fell in step with us, asking us where we were from.

Whether motivated by simple friendliness or gratitude after I bought two silk scarves at his shop, or probably some combination thereof, Kadir proceeded to show us the Udaipur we’d been craving: a glimpse of the busy bazaars frequented by the town’s residents. On the back of his motorbike we whizzed to the spice market, brilliant with turmeric, red chili and the other staples of Indian cooking, where I admired brightly labeled cans of cooking oil and countless varieties of dal and rice. Then we flew through the backstreets again (“Don’t worry, I’m the best driver in India,” Kadir called over his shoulder.) As night fell, we visited the mundi – a market located near the elephant gate that sells any conceivable item you could need.

As it happened, Richard Gere was in town filming the second installment of The Best Exotic Marigold Hotel (Judi Dench and Maggie Smith had been wandering around town the previous week as well, we heard from Kadir), a fact we heard from the tailor Kadir claimed was the best in town, who showed us a fuchsia-lined suit he said the actor had commissioned.

That night while digging into a delicious Rajastani goat stew known as laal mass at Ambrai restaurant in the marvelous Amet Haveli hotel, which offered views of the City Palace and the Taj Lake Palace (a onetime island noble home that is now Udaipur’s most exclusive hotel – much of the James Bond classic Octopussy was filmed there), we had proof. There, 10 feet from our table, sat Gere himself. The sparkling river, glowing palaces, and presence of a movie star provoked a momentary “Where am I?” vertigo. But after 10 days in India, I’d come to regard that feeling as completely normal.

Read more Fantasy Travel Week stories on Food Republic: