Caltransin varhaisimpana edeltäjänä oli Bureau of Highways, jonka Kalifornian lainsäätäjä perusti ja jonka kuvernööri James Budd allekirjoitti laiksi vuonna 1895. Tämä virasto koostui kolmesta komissaarista, joiden tehtävänä oli analysoida osavaltion tiejärjestelmää ja antaa suosituksia. Tuohon aikaan osavaltion valtatiejärjestelmää ei ollut olemassa, sillä tiet olivat puhtaasti paikallisen tason vastuulla. Kalifornian tiet koostuivat piirikuntien ylläpitämistä karkeista hiekkateistä sekä joistakin päällystetyistä kaduista tietyissä kaupungeissa, eikä tämä tilapäinen järjestelmä enää riittänyt osavaltion nopeasti kasvavan väestön tarpeisiin. Sen jälkeen kun komission jäsenet olivat toimittaneet raporttinsa kuvernöörille 25. marraskuuta 1896, lainsäätäjä korvasi toimiston maanteiden osaston (Department of Highways) nimellä.
Tosavaltion heikon verotilanteen ja korruptoituneen politiikan vuoksi edistystä tapahtui vain vähän ennen vuotta 1907, jolloin lainsäätäjä korvasi maanteiden osaston (Department of Highways) insinööriministeriöllä (Department of Engineering), jonka yhteydessä oli maanteiden osasto (Division of Highways). Kalifornian äänestäjät hyväksyivät 18 miljoonan dollarin joukkovelkakirjalainan osavaltion moottoritiejärjestelmän rakentamista varten vuonna 1910, ja Kalifornian ensimmäinen tiekomissio kutsuttiin koolle vuonna 1911. Elokuun 7. päivänä 1912 osasto aloitti ensimmäisen rakennushankkeensa, Etelä-San Franciscon ja Burlingamen välisen El Camino Realin osuuden, josta tuli myöhemmin osa Kalifornian osavaltion valtatietä 82, rakentamisen. Vuonna 1912 perustettiin myös liikennelaboratorio ja seitsemän hallinnollista osastoa, jotka ovat vuonna 2018 käytössä olevien 12 piiritoimiston edeltäjiä. Alkuperäiset seitsemän osaston pääkonttorit sijaitsivat:
- Willits Mercantile Building Del Norten, Humboldtin, Laken ja Mendocinon piirikunnille
- Redding C.R.Briggs Building Lassenin, Modocin, Shastan, Siskiyoun, Tehaman ja Trinityn piirikunnissa
- Sacramento Forum Building Alpinen, Amadorin, Butten, Calaverasin, Colusan, El Doradon, Glennin, Nevadan, Nevadan, Placerin, Plumasin, Sacramenton, San Joaquinin, Sierran, Solanon ja Stanislauksen piirikunnissa, Sutter, Tuolumne, Yolo ja Yuban piirikunnat
- San Francisco Rialto Building Alamedan, Contra Costan, Marinin, Napan, San Franciscon, Santa Claran, Santa Cruzin, San Mateon ja Sonoman piirikunnat
- San Luis Obispo Union National Bank Building Montereyn piirikunta, San Benito, Santa Barbara ja San Luis Obispon piirikunnat
- Fresno Forsythe Building Fresnon, Inyon, Kernin, Kingsin, Maderan, Mariposan, Mercedin, Monon ja Tularen piirikunnat
- Los Angeles Union Oil Building Imperialin, Los Angelesin, Orange, Riverside, San Bernardino, San Diego ja Ventura counties
Vuonna 1913 Kalifornian osavaltion lainsäätäjä alkoi vaatia ajoneuvojen rekisteröintiä ja osoitti siitä saatavat varat maanteiden säännölliseen kunnossapitoon.
Vuonna 1921 osavaltion lainsäätäjä muutti insinööriosaston julkisten töiden ministeriöksi.
Caltransin ja sen edeltäjien historiaa 1900-luvulla leimasivat monet ensikertalaisuudet. Se oli yksi ensimmäisistä virastoista Yhdysvalloissa, joka maalasi valtateiden keskilinjat osavaltion laajuisesti; ensimmäinen, joka rakensi moottoritien Mississippi-joen länsipuolelle; ensimmäinen, joka rakensi nelitasoisen liittymän; ensimmäinen, joka kehitti ja otti käyttöön heijastamattomat korotetut päällystemerkinnät, jotka tunnetaan paremmin nimellä Bottsin pisteet; ja yksi ensimmäisistä, joka otti käyttöön moottoriteiden ja valtateiden väliset liittymärampit suurten ajoneuvojen kaistoja varten.
Kuvernööri Ronald Reagan perusti vuonna 1967 liikennettä käsittelevän työryhmän (Task Force Committee on Transportation), jonka tehtävänä oli tutkia valtion liikennejärjestelmää ja suositella merkittäviä uudistuksia. Yksi työryhmän ehdotuksista oli osavaltion liikennepolitiikan pysyväksi neuvoa-antavaksi lautakunnaksi perustettava osavaltion liikennelautakunta; lautakunta sulautui myöhemmin Kalifornian liikennekomissioksi vuonna 1978. Syyskuussa 1971 osavaltion liikennelautakunta ehdotti osavaltion liikenneministeriön perustamista, jonka tehtävänä olisi ”kaikkien liikennemuotojen liikennesuunnittelun toteuttaminen ja integrointi”. Kuvernööri Reagan mainitsi tämän ehdotuksen vuoden 1972 osavaltion tilaa koskevassa puheessaan, ja edustaja Wadie P. Deddeh esitti asiaa koskevan lakiehdotuksen 69, jonka osavaltion lainsäätäjä hyväksyi asianmukaisesti ja jonka Reagan allekirjoitti laiksi myöhemmin samana vuonna. AB 69:ssä yhdistettiin kolme olemassa olevaa osastoa liikenneministeriöksi, joista tärkein oli yleisten töiden osasto (Department of Public Works) ja sen valtatieosasto (Division of Highways). Kalifornian liikenneministeriö aloitti virallisen toimintansa 1. heinäkuuta 1973.