I never met the last Begum of Avadh, but I probably walked past her a few times on the way to the chai- wallah. According to a small news item I spotted a few years ago, the first lady of one of India's largest princely states had lived the last decade of her life in the waiting room of New Delhi railway station. Her existence, I read, had been brought to an end by a lethal dose of diamond dust and poison, self-administered.

Death by diamond dust. There was something vaguely reminiscent of James Bond and Goldfinger about it. I had been in the waiting room at New Delhi several times and if I had failed to spot the Begum it was probably because there was a considerable population in there at the time. But the story fascinated me. I think it was the mixture of diamonds, ruined royalty and the railway.

And then it was at the gate of the same station that I fell in with a bad crowd one night, got talking and dropped my guard. They knew me, I realised afterwards; knew that I was someone interested in diamonds, possibly someone who had been buying up stock in Surat and Bombay. We shared a packet of ginger biscuits, the type sold on every station platform in India.

I don't remember the biscuit tasting strangely, only a point where it was soft, but by then I had swallowed and it was too late. My head fell back and hit a metal stanchion. I was found two days later, lying in a monsoon drain, my bag next to me with each of its seams neatly slit open and anything of value gone.

Like most people, I had always thought of diamonds as an African product - one that has singularly failed to benefit the majority of Africans, but nevertheless something that came from Sierra Leone, Liberia, Angola or South Africa.

It was only when I began to trawl through the libraries that I began to notice that all the great old diamonds - the ones with wonderful romantic sagas and blood-curdling curses attached - were all connected with India.

The single stone that stands out, is of course, the Koh-i-Noor, and one day, reading a history of its dramatic career, I started plotting its course on a map. From that rough sketch came the idea for a journey: through India on the trail of a diamond. And it was the Begum's lifeless corpse on platform 1a that gave me the means: the Indian train. Somehow diamonds and railways were the right combination.

I started my diamond journey in Madras, a city founded by the East India Company and whose fort was the largest single building the British ever put up in the sub-continent. Far from being there only for spices, the company men were preoccupied with the diamonds that came down, illicitly, from the area known as Golconda, now Hyderabad. The stones were the perfect way for an ambitious and unscrupulous officer to line his own pocket - something that the son of a Dorset vicar, one Thomas Pitt, did with alacrity, thus founding a dynasty that would produce the two famous prime ministers.

The ancient mines - once the only source of the world's diamonds - were located somewhere on the Krishna River between Madras and Hyderabad. A government geologist assured me that diamonds were no longer present, but his driver knew better. He took me to meet a local villager who nodded at my questions about old mines and told me that the Koh-i-Noor had been found nearby. He went into his hut and returned with a small silk purse. Telling me to hold out my hand, he shook the contents out: half-a-dozen rough uncut diamonds.

I remember my fingers trembling. All that travelling and now I had found what I wanted: the beginning of a journey, the place where the old diamonds originated.

From there, I headed across the Deccan to Pune and Bombay, then north up to Surat and on into Gujarat. Indian railways are not chaotic: they have preserved an old-fashioned sense of order and time-keeping that is impressive. The only problem is that they are too successful, inundated with passengers - more than 12 million a day.

I usually preferred the second-class sleepers. In first, you get air-conditioning, which is clearly designed to create a hill station on wheels, but I prefer the heat. Also, you meet fewer people, though the seclusion can allow confidences. One night on the Bombay Express, two shady characters who claimed to be social workers gradually let their guard slip and I found we were after the same quarry: diamonds.

The whole of the coast north of Bombay, they told me, had gone diamond mad. Every village boy dreamed of making his fortune with them. The great advantage was that literacy and paper qualifications were irrelevant; what was required was a modicum of skill at assessing stones and plenty of cunning. In the Gujarati town of Palitana, I met schoolboys whose hero was not a Bollywood star or cricketer, but their illiterate grandfather who had gone to Antwerp and become a millionaire.

If one stone epitomises the glamour of diamonds, it is the Koh-i-Noor and my route led me to places where it had associations. Some were obvious, though no less interesting: the Taj Mahal built for Shah Jehan's wife, Mumtaz Mahal; and Agra Fort, where he was imprisoned by his own son Aurangzeb.

Further up the Jumna River is Ram Bagh, the garden first laid out by Babur, Shah Jehan's great-great-grandfather and the founder of the Mogul empire. There, smelling of earth and water, are the ruins of Babur's summer retreat: a place of subterranean fountains and pools, all abandoned to the rats and spiders.

It was Babur who captured a great jewel at Agra - equal in value to "two and a half days' food for the whole world". Quite probably this was the Koh-i-Noor, but Babur had no time for baubles. He gave it away to his son, Humayun. When the son fell ill, Babur's advisers begged him to offer the diamond as a sacrifice. But the emperor decided that the stone was not sufficient and offered his own life. According to legend, he died soon afterwards. Humayun, newly recovered, lost the empire anyway and was forced to flee westwards.

My own route turned that way, too. I rode into Kathiawar, the broad peninsula that hangs like a jewel under the nose of land jutting out towards Pakistan.

There are places where it seems that there is no need to keep skating across the surface of the country, a single vertical shaft sunk through the layers of accumulated history of one place will be more rewarding. Junagadh is such a spot.

I discovered that the ruling Nawab, who had fled at Partition, had once held a dog wedding between his favourite bitch, Roshanara, and a golden retriever from Bangalore called Bobby. Eventually, by simply staying long enough, I bumped into a man whose grandfather had attended the ceremony back in the 1920s.

"The bride and groom wore silk gowns," he told me. "They had gold chains on their paws and necklaces of jewels."

Large numbers of guests attended, and dancing girls were brought from Bombay. On the wedding night, however, the Nawab became jealous and had Bobby thrown in the common kennels so Roshanara could sleep on his bed.

My local friend took me to meet the Nawab's relatives whose reduced circumstances were starkly revealed: the rooms in their palace had been sold off one by one until it was no more than a tenement block with themselves huddled in the middle.

Leaving Junagadh behind, the route of the Koh-i-Noor took me northwards to Gwalior, Agra and Delhi. At all times people wanted to talk.

"What is your family name?"

"Why?"

"Perhaps we are related."

Snatches of crazed conversation. Notebooks and diaries full and overflowing.

"Sir! My lady says this is vanishing cream." A tube of ointment thrust into my hand. I see it is in Greek, but I can't see the woman in question.

"What lady?"

He turns, frowns and hurries away, never to be seen again by me, possibly anyone.

In Delhi, I met with my disaster. So many fleeting relationships built up on journeys that I could no longer maintain the initial suspicion that both protects and isolates a traveller. And afterwards, my first reaction was to get on a train, to move again and hear the comforting clickety-clack of the wheels and the sudden deepening "aaooh" when the iron bridge starts and a vast river is far below.

After dark, there is nothing so magical as being on a sleeper train somewhere in India. It pulls into a small station where the platform is full of people wrapped in shawls, walking up and down to keep warm or huddled around a brazier. Then the chai-wallah comes along with his mournful cry and serves cups of tea through the bars of the carriage windows.

Sometimes the cups are sun-fired mud and, if you drink too slowly, the soft silty taste of India itself seeps into the brew. But no one really buys it for the taste: they buy it so they can smash the cup down as the train hoots and pulls away.

Then a dozen arms reach out and the cups make a lovely pop as they hit the wooden sleepers, a noise that champagne manufacturers have been trying to emulate for years but never quite mastered - the sound of an Indian train celebrating its own departure.

How to survive Indian trains

* Buy tickets as far in advance as possible, as popular services get booked up. Also watch out for the start and finish of the school holidays.

* Some trains have foreigner quotas, payable in hard currency. You don't have to use them, however: join the throng and pay in rupees.

* A locking bag with chain to attach it to your berth can discourage sneak thieves.

* Bottled water is available in much of India. Check the seal is not broken.

* Remember that trains can vary enormously in the speed they travel, slower services taking days to do what others achieve in a few hours.

* Sheets and pillow only come with first class, so take what you need for second.

* Have a plan when arriving. Wandering around like a lost sheep guarantees a slaughter. Waiting rooms are good, safe havens where you can pass a few hours to think what to do. But if you meet a deposed Begum, don't share the crushed diamond juice.

• Kevin Rushby is the author of Chasing the Mountain of Light, Across India on the Trail of the Koh-i-Nor Diamond, published by Flamingo at £7.99.

The practicals

Air India (020-7495 9750) has return fares from Heathrow to Delhi for £950. Virgin Atlantic (01293 747747) flies Heathrow to Delhi from £520.50 inc tax. Indrail passes are bookable in advance in the UK at SD Enterprises (020-8903 3411, www.dandpani.dircon.co.uk). A first-class air-conditioned 15-day pass costs £124 for any number of journeys (allow one month's notice), second class, £60 (allow three months). Other time periods are available. Timetables available for £5 from SD Enterprises or visit the website.