Source (Unable to produce a soft copy) - Report by the Railway Board on Indian Railways, 1925-26, Vol I
Prior to 1925, there were two daily mail/express trains from Bombay to Ahmedabad. These were the over-night Gujarat mail from Bombay to Ahmedabad, and the day-time Kathiawar express from Bombay to Viramgam.
Owing to the over-crowding on the Gujarat mail, which was the preferred train for going to Ahmedabad, as the Kathiawar express was a day-time train, and slower by 2.5 hours compared to the mail, the Bombay, Baroda and Central Indian Railway (B.B&C.I.R)...
more... decided to run two over-night mail trains instead of one.
As a result, from 1st October, 1925, the Kathiawar mail was introduced between Bombay Colaba terminus and Viramgam. This was a sister train to the Gujarat mail and followed a similar schedule to the older mail.
Sometime after independence, the mail was renamed as the 'Saurashtra mail'. In the timetable that came into effect from 1st November, 1980, it was extended to Hapa. Following the gauge conversion of the route till Okha in 1984, the train was further extended to Okha.