Trujillo เริ่มต้นอาชีพธุรกิจในปี 1974 ในฐานะนักพยากรณ์เศรษฐกิจใน แผนก Mountain BellของAT&Tเมื่ออายุ 32 ปี Trujillo ได้รับเลือกเป็นรองประธานรัฐ และประธานเจ้าหน้าที่บริหารของการดำเนินงานของ Mountain Bell ในนิวเม็กซิโก ทำให้เขากลายเป็นเจ้าหน้าที่ที่อายุน้อยที่สุดในประวัติศาสตร์ของ AT&T ^{[ 8 ]}

ในปี พ.ศ. 2539 Trujillo ได้รับการแต่งตั้งเป็นประธานของUS Westเขาได้รับการเลื่อนตำแหน่งเป็นประธานและซีอีโอในปี พ.ศ. 2541 กลายเป็นซีอีโอเชื้อสายลาตินที่เกิดในอเมริกาคนแรกของบริษัท Fortune 200 ^{[ 9 ] [ 4 ]}

Trujillo ลาออกจากตำแหน่ง CEO ของ US West ในปี 2545 หลังจากการควบรวมกิจการของบริษัทกับ Joe Nacchio CEO ของ Qwest Communications โดยอ้างถึงความแตกต่างในวิสัยทัศน์ระหว่างทั้งสอง ในช่วงที่เขาดำรงตำแหน่งที่บริษัท Trujillo ได้รับการยกย่องว่าได้เปลี่ยนชื่อเสียงของ US West จาก "เครือข่ายโทรศัพท์ท้องถิ่นที่เล็กที่สุด" ให้กลายเป็นเครือข่ายที่มุ่งเน้นอินเทอร์เน็ตความเร็วสูงและเทคโนโลยีอื่นๆ เช่นVoice over IP ^{[ 10 ]}

ในเดือนพฤศจิกายน พ.ศ. 2543 Trujillo ได้ดำรงตำแหน่งประธานและซีอีโอของ Graviton ซึ่งเป็น บริษัทสตาร์ทอัพใน La Jollaที่ผลิตเทคโนโลยีเซ็นเซอร์ที่เชื่อมต่อแบบไร้สายสำหรับการใช้งานสาธารณะและส่วนตัว^{[ 11 ]}เขาได้รับการชักชวนโดย Brook Byers ผู้อำนวยการของKleiner Perkins Caufield & Byersนอกจาก Kleiner Perkins แล้ว นักลงทุนรายอื่น ๆ ในบริษัทสตาร์ทอัพซึ่งระดมทุนได้มากกว่า 60 ล้านดอลลาร์สหรัฐ ยังรวมถึง Qualcomm, Siemens, Royal Dutch/Shell Group In-Q-Telและ Sun Microsystems ^{[ 12 ] [ 13 ]}

Trujillo ออกจากบริษัทไม่นานก่อนที่บริษัทจะถูกขายให้กับ Xsilogy ซึ่งเป็นบริษัทเซ็นเซอร์และตรวจสอบแบบไร้สายอีกแห่งหนึ่ง ด้วยจำนวนเงินที่ไม่เปิดเผย^{[ 14 ] [ 5 ] [ 15 ]}

หลังจากดำรงตำแหน่งเป็นสมาชิก คณะกรรมการบริหาร ของ Orange SA เป็นเวลาสองปี Trujillo ได้รับการแต่งตั้งให้เป็น CEO ของบริษัทในปี 2546 เขาเป็นชาวอเมริกันคนแรกที่นำบริษัทCAC 40 ^{[ 4 ]}

ที่ออเรนจ์ ทรูจิลโลดำเนินกลยุทธ์การเติบโตเชิงรุกเพื่อต่อสู้กับภาระหนี้สินจำนวนมากที่เขาได้รับสืบทอดมา^{[ 16 ] [ 17 ]}ซึ่งขัดแย้งกับทิศทางธุรกิจของ France Telecom บริษัทแม่ของออเรนจ์ซึ่งเป็นของรัฐ และในที่สุดก็เข้าซื้อหุ้นของผู้ถือหุ้นรายย่อยและควบรวมกิจการ^{[ 18 ]}

Trujillo ลาออกจากตำแหน่ง CEO ของ Orange ในเดือนมีนาคม พ.ศ. 2547 โดย "ได้บรรลุภารกิจตามที่ได้รับมอบหมาย" และเดินทางกลับสหรัฐอเมริกา ภายใต้การนำของเขา Orange มีลูกค้าเพิ่มขึ้น 5 ล้านราย และอัตรากำไรจากรายได้เพิ่มขึ้น 10 และ 7 เปอร์เซ็นต์ตามลำดับ^{[ 18 ]}

Trujillo ได้รับการแต่งตั้งเป็นประธานเจ้าหน้าที่บริหารของTelstra Communications ซึ่งเป็นบริษัทโทรคมนาคมและสื่อที่ใหญ่ที่สุดของออสเตรเลีย เมื่อวันที่ 1 กรกฎาคม พ.ศ. 2548 ^{[ 19 ]}ท่ามกลางข่าวการแต่งตั้งของเขาThe Economistได้ตั้งชื่อตำแหน่งนี้ว่า "งานองค์กรที่ยากที่สุดของออสเตรเลีย" เนื่องจากภารกิจของ Trujillo คือการเตรียมบริษัทให้พร้อมสำหรับการเสนอขายหุ้นต่อสาธารณะ ครั้งใหญ่ที่สุด ในประวัติศาสตร์ของ ออสเตรเลีย ^{[ 20 ]}บริษัทดังกล่าวซึ่งเดิมชื่อ Telecom Australia เดิมเป็นของรัฐ แต่ได้ขายหุ้นส่วนน้อยออกไประหว่างปี พ.ศ. 2540 ถึง พ.ศ. 2542 ระดมทุนได้ประมาณ 30 พันล้านดอลลาร์ออสเตรเลีย ในขณะที่ Trujillo ได้รับการแต่งตั้ง บริษัทประมาณ 51.8 เปอร์เซ็นต์ยังคงเป็นของรัฐบาล ซึ่งการขายได้เสร็จสิ้นลงอย่างประสบความสำเร็จในราคา 15.5 พันล้านดอลลาร์ออสเตรเลียในปี พ.ศ. 2549 ^{[ 20 ]}

ราคาหุ้นของ Telstra ต่ำกว่าที่คาดการณ์ไว้เนื่องจากการเสนอราคาที่คำนวณผิดพลาดในช่วงที่Ziggy Switkowski อดีตซีอีโอของบริษัทดำรงตำแหน่ง ซึ่งรวมถึงการซื้อกิจการ CSLผู้ให้บริการโทรศัพท์มือถือในฮ่องกงและความพยายามซื้อกิจการJohn Fairfax Holdingsซึ่งเป็นหนังสือพิมพ์ขนาดใหญ่ของออสเตรเลีย^{[ 20 ]}ธุรกิจโทรคมนาคมของรัฐถูกอธิบายว่า "เชื่องช้า" และล้าหลังคู่แข่งก่อนที่จะแปรรูปเป็นเอกชนอย่างสมบูรณ์ เนื่องจากธุรกิจโทรศัพท์พื้นฐานถูกคู่แข่งอย่างบริการอินเทอร์เน็ตและโทรศัพท์มือถือแย่งส่วนแบ่งตลาดไป^{[ 21 ] [ 22 ]}

หลังจากได้รับการแต่งตั้ง ทรูจิลโลได้ประกาศแผนฟื้นฟูธุรกิจระยะ 5 ปีโดยอิงจาก "หลักการ" เพื่อทำให้บริษัทตอบสนองต่อข้อกังวลของผู้ถือหุ้นได้ดียิ่งขึ้น^{[ 23 ]}นอกจากการพยายามปรับปรุงระบบของบริษัทและลดจำนวนพนักงานแล้ว ทรูจิลโลยังพยายามอัปเกรดเครือข่ายและระบบที่ล้าสมัย^{[ 24 ]}ซึ่งนำไปสู่การใช้งาน อินเทอร์เน็ตมือถือ 3G 850  MHz ทั่วประเทศเพื่อทดแทนเครือข่ายมือถือ CDMA ที่ใช้ในขณะนั้น^{[ 25 ]}เครือข่ายนี้สร้างขึ้นระหว่างเดือนพฤศจิกายน 2548 ถึงเดือนกันยายน 2549 และเปิดตัวในเดือนตุลาคม 2549 เครือข่ายที่ใหญ่ที่สุดและเร็วที่สุดในโลกนี้ทำให้ปริมาณการรับส่งข้อมูลทั้งหมดบนเครือข่ายไร้สายของ Telstra เพิ่มขึ้นเป็นสองเท่า^{[ 26 ]}หลังจากดำรงตำแหน่งได้ 3 ปี ทรูจิลโลได้รับการยกย่องให้เป็น "ซีอีโอแห่งปี" โดยนิตยสาร Australian Telecom Magazine เพื่อเป็นการยกย่องความสำเร็จของเขาในการแปรรูปและเปลี่ยนแปลง Telstra ^{[ 27 ]}

แม้จะประสบความสำเร็จ แต่ Telstra ก็ประสบปัญหาด้านกฎระเบียบซ้ำแล้วซ้ำเล่าในขณะที่พยายามขยายธุรกิจ ในเดือนสิงหาคม พ.ศ. 2549 ข้อพิพาทด้านกฎระเบียบทำให้ Telstra ต้องยกเลิกโครงการสร้างเครือข่ายใยแก้วนำแสงความเร็วสูงใน 5 เมืองใหญ่ที่สุดของประเทศ หลังจากเกิดความไม่ลงรอยกันเกี่ยวกับจำนวนเงินที่บริษัทสามารถเรียกเก็บจากคู่แข่งสำหรับการเข้าถึงเครือข่ายได้^{[ 24 ]}ด้วยความตระหนักถึงหน้าที่ที่มีต่อผู้ถือหุ้น Trujillo จึงขู่ว่าจะไม่สร้างเครือข่าย: "หน้าที่ของผมคือต่อผู้ถือหุ้นของเรา ซึ่งรวมถึงชาวออสเตรเลียทั่วไป 1.6 ล้านคน ผมจะลงทุนเฉพาะที่ที่ผมสามารถสร้างผลตอบแทนทางเศรษฐกิจได้เท่านั้น" ^{[ 22 ]}

หลังจากการเสนอราคาที่มีชื่อเสียง บริษัทถูกถอดออกจากกระบวนการประมูลเพื่อสร้างเครือข่ายบรอดแบนด์ความเร็วสูงระดับชาติโดยรัฐบาลรัดด์ [ ^{28 ] [ 29 ] [ 30 ] ใน}เดือนกุมภาพันธ์ 2552 ทรูจิลโลประกาศว่าเขาจะลาออกจากตำแหน่งซีอีโอของเทลสตราและกลับไปยังสหรัฐอเมริกา^{[ 31 ]}เขาถูกแทนที่ในตำแหน่งซีอีโอโดยเดวิด ธอดีย์อดีตหัวหน้าฝ่ายกิจการรัฐบาลของบริษัท ซึ่งยืนยันว่าเขาวางแผนที่จะดำเนินการตามแผนห้าปีของทรูจิลโลให้เสร็จสิ้น^{[ 32 ] [ 30 ] [ 33 ]}

Trujillo ได้รับการยอมรับว่าเป็น CEO ที่ชอบต่อสู้และมักขัดแย้งกับรัฐบาลออสเตรเลีย แต่มีบทบาทสำคัญในการเปลี่ยนสถานะของ Telstra จากการผูกขาดที่รัฐบาลควบคุมไปสู่บริษัทที่มีความคล่องตัวและแข่งขันได้มากขึ้น^{[ 34 ] [ 35 ]}

Trujillo เข้าร่วมทีมผู้บริหารของบริษัทสตาร์ทอัพโทรศัพท์มือถือ Unlockd ของออสเตรเลียในเดือนกรกฎาคม 2016 บริษัทสตาร์ทอัพดังกล่าวระดมทุนได้ 12 ล้านดอลลาร์สหรัฐในรอบSeries Aโดยร่วมมือกับบริษัทโทรคมนาคมเพื่อแสดงโฆษณาบนอุปกรณ์ของผู้บริโภคเพื่อแลกกับส่วนลดค่าบริการรายเดือน^{[ 36 ] [ 37 ]}